e-olymp
Competitions

IATI2019 Azerbaijan selection round based on Croatian Open Olympiad Round 3 2011/2012

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.

Time limit 1 second
Memory limit 32 MiB
Input example #1
1 3
0 -10
ISI
Output example #1
11
12
13
Input example #2
3 5
0 0
1 1
1 -1
SIJJZ
Output example #2
5
4
3
4
5
Source IATI2019 Azerbaijan Selection based on Croatian Open Olympiad Round 3 2011/2012