Description

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.

Input Format

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 Format

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).

3 3
0 0
4 -3
6 7
x
m -1 2
y

1 2
-3 5
-5 -5

Hint

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