e-olymp

Robot

Ibrahim created a new robot and decided to test it on a giant test track. We can imagine the test track as 2D coordinate system. The robot starts at a point (0,0) and receives a set of instructions denoted by letters S, J, I, Z, each of them marking a direction in which robot should be moving. More precisely, if a robot is located in (x,y) , S (“north”) means it should move to (x,y+1), J(“south”) means it should move to (x,y-1), I(“east”) means it should move to (x+1,y) and Z(“west”) means it should move to (x-1,y). While robot is receiving instructions and moves through the test track, Ibrahim is verifying its position in the following manner. Test track contains N fixed control points. After each instruction is made, each of the control points measures manhattan-distance to the robot. Distances from all control points are then summed and sent to Ibrahim. Assuming that robot moves by the instructions without error, calculate the sum of distances to all control points after each instruction. Remark: manhattan-distance of the points (x1,y1) and (x2, y2) is equal to |x1 - x2| + |y1 – y2|.

Input:

First line of input contains positive integers N (**number of control points**, 1N100 000) and M (**number of instructions**, 1M300 000), separated by a single space. Each of the following N lines contains coordinates of one control point: two space-separated integers x, y, with absolute value less than 1 000 000 (million). It is possible that two control points have the same coordinates - distance towards each of them is added to the sum. The following line contains a string of M characters from the set {S, J, I, Z}, the sequence of instructions sent to the robot.

Output:

Output M lines: i-th line of output should contain the described number after i-th instruction.

Лимит времени 1 секунда
Лимит использования памяти 32 MiB
Входные данные #1
1 3
0 -10
ISI
Выходные данные #1
11
12
13
Входные данные #2
3 5
0 0
1 1
1 -1
SIJJZ
Выходные данные #2
5
4
3
4
5
Источник IATI2019 Azerbaijan Selection based on Croatian Open Olympiad Round 3 2011/2012