|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
There are $N$ ($ 1 \le N \le 10^5 $) points in the plane, represented by the pair $ (x_i, y_i) $ for the $i$-th point. Each point can be in only one of two states: active or inactive. Initially, all points are active. To these, a series of operations are applied, which are described below:
- $R$ $a$
The active points are rotated by $ a $ degrees with respect to the origin $ (0,0) $, counterclockwise. The value of $ a $ will be integer and comply the following constraints: $ a \in \{0, 90, -90, 180, -180, 270, -270\}$.
- $T$ $ t_x $ $ t_y $
All active points are translated: let $ (x_i, y_i) $ be an active point, then its new value becomes $ (x_i + t_x, y_i + t_y) $. The values of $ t_x $ and $ t_y $ will be integers and comply the following constraints: $ -5 \times 10^4 \le t_x , t_y \le 5 \times 10^4 $.
- $M$ $ m_x $ $ m_y $
The following scaling operation is applied to all active points: let $(x_i, y_i) $ be an active point, then its new value becomes $(x*m_x, y*m_y) $. The values of $ m_x $ and $ m_y $ will be integers and comply the following constraints: $ -5 \times 10^4 \le m_x , m_y \le 5 \times 10^4 $.
- $D$ $ d_x $ $ d_y $
The following scaling operation is applied to all active points: let $(x_i, y_i) $ be an active point, then its new value becomes $(x_i/d_x, y_i/d_y)$. It is ensured that $ x_i $ is divisible by $ d_x $ and that $ y_i $ is divisible by $ d_y $. The values of $ d_x $ and $ d_y $ will be integers and will fit the range $ -5 \times 10^4 \le d_x , d_y \le 5 \times 10^4 $.
- $B$ $i$
The $i$-th point becomes inactive if it is active, and active if it is inactive. If a point is inactive, the operations described above have no effect on it.
- $P$ $i$
The coordinates of the $i$-th point should be printed, regardless of its active status.
Input
The first line contains integer $N$ ($ 1 \le N \le 10^5 $) the total number of points and integer $Q$ ($ 1 \le Q \le 10^5 $) the number of operations.
The following $N$ lines contain two integers $ x_i, y_i $ ($
-5 \times 10^4 \le x_i, y_i \le 5 \times 10^4 $) these being the $x$ and $y$
values of the $i$-th point $ (1 \le i \le N )$.
The following $Q$ lines contain the operations to be performed on the points. At the beginning is the character $ c_i \in {R, T, B, M, D, P}$ and separated by a space, one or two integers in accordance to the operation to be performed. See the previous section for more details.
Output
For each print operation (those denoted by the character $ P $) in the same order in which they are requested, a line must be printed with the x and y coordinates of the point to be operated.
Sample test(s)
Input
5 12
0 0
1 1
2 2
3 1
-2 -5
R 90
B 5
T 5 0
B 4
B 1
R -90
B 5
B 1
T -3 0
B 4
T -1 -1
P 1
Output
1 -1
Input
4 19
1 1
1 -1
-1 -1
-1 1
M 2 2
B 4
B 3
D 2 1
T 3 2
B 3
D 2 2
P 1
B 2
P 4
B 4
R 180
B 3
B 2
D 2 2
P 1
P 2
P 3
P 4
Output
2 2
-2 2
-1 -1
1 0
1 1
1 -1