P2129 The Battle of Country L Continues: Multi-route Offensive

Public notice: see the background in other “The Battle of Country L” problems. Let’s solve them together.

This time, Country L decides to divide its army into $n$ groups distributed across various locations. Taking Country L as the origin, these positions can be viewed in a Cartesian coordinate system. All groups are under unified command, and the command center issues $m$ commands. Commands include translation, up-down flip, and left-right flip. However, due to some odd latency, the army always receives commands with a delay. For convenience, a stack has already been prepared, so you must process the commands from back to front.

The input consists of $n+m+1$ lines. The first line contains two integers $n, m$. The next $n$ lines: on the $(i+1)$-th line, two integers $x_i, y_i$ give the location of the $i$-th army group. The next $m$ lines each start with a character $c$. - If $c$ is `m`, then two integers $p, q$ follow, meaning every group moves from $(x_i, y_i)$ to $(x_i + p, y_i + q)$. - If $c$ is `x`, then every group moves from $(x_i, y_i)$ to $(-x_i, y_i)$ (left-right flip, i.e., reflection across the $y$-axis). - If $c$ is `y`, then every group moves from $(x_i, y_i)$ to $(x_i, -y_i)$ (up-down flip, i.e., reflection across the $x$-axis).

Output $n$ lines. On the $i$-th line, print two integers $x_i', y_i'$, the final position of the $i$-th army group after all commands are applied (processed from last to first).

For $30\%$ of the testdata, $1 \leqslant n, m \leqslant 1000$. For $100\%$ of the testdata, $1 \leqslant n, m \leqslant 5 \times 10^5$, and $x_i, y_i$ are within the `int` range. Translated by ChatGPT 5