P9430 [NAPC-#1] Stage2 - Darkness

> 

There are $n$ armies distributed in different places, which can be viewed on a 2D Cartesian coordinate system. They are all under kid’s unified command, and kid issues a total of $m$ commands. The commands are as follows: - `1 p q` means moving the position of **every** army from $(x_i,y_i)$ to $(x_i+p,y_i+q)$. - `2 i` means applying an axis symmetry (reflection) of the position of **the $i$-th army** over the line $y=x$ (i.e., swapping the values of $x_i$ and $y_i$). - `3 i` means querying the current position of the $i$-th army (i.e., output the current $x_i$ and $y_i$). **Note that commands `1` and `2` operate on different targets: the former affects all armies, while the latter affects only one army.** kid could have used binoculars to see directly, but it is too dark, so he asks you to write a program to tell him.

The first line contains two positive integers $n,m$. The next $n$ lines: the $i$-th line contains two integers $a_i,b_i$, representing the initial position of the $i$-th army $(x_i,y_i)=(a_i,b_i)$. The next $m$ lines: each line contains two or three integers, representing a command issued by kid. Specifically, each command starts with a positive integer $op$ indicating the command type: - If $op=1$, then two integers $p,q$ follow, meaning moving the position of **every** army from $(x_i,y_i)$ to $(x_i+p,y_i+q)$. - If $op=2$, then a positive integer $i$ follows, meaning applying an axis symmetry of **the $i$-th army** over $y=x$. - If $op=3$, then a positive integer $i$ follows, meaning querying the current position of the $i$-th army.

For each `3` command issued by kid, output one line with two integers $x_i,y_i$, representing the current position of the $i$-th army.

### Constraints This problem has $10$ test points, and each test point has equal score. - For $20\%$ of the testdata, $n,m\leqslant 1000$. - For another $30\%$ of the testdata, it is guaranteed that there are no `2` commands. For $100\%$ of the testdata, $1\leqslant n\leqslant 10^5$, $1\leqslant m\leqslant 5\times10^5$, $|a_i|,|b_i|,|p|,|q|\leqslant 10^3$, $1\leqslant i\leqslant n$, $op\in\{1,2,3\}$. ### Sample Explanation | Time | $(x_1,y_1)$ | $(x_2,y_2)$ | $(x_3,y_3)$ | | :-: | :-: | :-: | :-: | | Initial | $(1,2)$ | $(2,5)$ | $(6,2)$ | | After the 2nd command | $(2,6)$ | $(3,9)$ | $(7,6)$ | | After the 4th command | $(2,6)$ | $(3,9)$ | $(6,7)$ | | After the 6th command | $(-7,5)$ | $(-6,8)$ | $(-3,6)$ | Translated by ChatGPT 5