Description

We can think of the test track as a 2D coordinate system. The robot starts from $(0,0)$ and receives a sequence of commands represented by S, J, I, Z. Each command tells the robot which direction to move. Specifically, if the robot is currently at $(x,y)$:

• Command S means it should move to $(x,y+1)$.
• Command J means it should move to $(x,y-1)$.
• Command I means it should move to $(x+1,y)$.
• Command Z means it should move to $(x-1,y)$.

While the robot receives commands and moves on the test track, Mirko checks its position in the following way:

There are $n$ fixed checkpoints on the test track. Each checkpoint measures the Manhattan distance to the robot, and sends the sum of all distances to Mirko. Assuming the robot moves exactly according to the commands, compute, after each command is executed, the sum of the Manhattan distances from all checkpoints to the robot.

Input Format

The input has $n+2$ lines.

The first line contains two integers $n,m$, representing the number of checkpoints and the number of commands.
Lines $2$ to $n+1$ each contain two integers $(x_i,y_i)$, representing the $x$-coordinate and $y$-coordinate of each checkpoint.
Line $n+2$ contains a string of length $m$, representing the commands the robot will receive.

Output Format

Output $m$ lines. Each line contains one integer, the sum of the Manhattan distances from all checkpoints to the robot after executing each command.

1 3
0 -10
ISI

11
12
13

3 5
0 0
1 1
1 -1
SIJJZ

5
4
3
4
5

Hint

[Prerequisite Knowledge]

• Manhattan distance: given two points $(a,b)$ and $(c,d)$, their Manhattan distance is $|a-c|+|b-d|$.

[Constraints]

For all testdata, $1\leqslant n\leqslant 10^5$, $1\leqslant m\leqslant 3\times 10^5$, $|x_i|,|y_i|\leqslant 10^6$. The commands contain only one of S, I, J, Z.

[Source]

This problem is from COCI 2011-2012 CONTEST 3 T4 ROBOT. Using the original testdata configuration, the full score is $120$ points.

Translated and organized by Eason_AC.

Translated by ChatGPT 5