P7745 [COCI 2011/2012 #3] ROBOT

Mirko created a new robot and decided to test it on a huge test track.

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.

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 $m$ lines. Each line contains one integer, the sum of the Manhattan distances from all checkpoints to the robot after executing each command.

**[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](https://hsin.hr/coci/archive/2011_2012/) [CONTEST 3](https://hsin.hr/coci/archive/2011_2012/contest3_tasks.pdf) T4 ROBOT_**. Using the original testdata configuration, the full score is $120$ points. Translated and organized by [Eason_AC](https://www.luogu.com.cn/user/112917). Translated by ChatGPT 5