Background

Problem Description

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.

Input Format

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.

Output Format

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.

3 7
1 2
2 5
6 2
3 2
1 1 4
3 3
2 3
3 1
1 -9 -1
3 3

2 5
7 6
2 6
-3 6

Hint

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

Translated by ChatGPT 5