E - Rotate and Flip 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 500 点

問題文

2 次元平面に N 個の駒が置かれています。駒には 1 から N までの番号が付いており、駒 i が置かれている座標は (X_i,Y_i) です。複数の駒が同じ座標に置かれている可能性もあります。

M 個の操作 \mathrm{op}_1, \ldots, \mathrm{op}_M を順に行います。操作は 4 種類あり、入力形式と操作の内容は以下の通りです。

  • 1：全ての駒を、原点を中心に時計回りに 90 度回転させた位置に移動する
  • 2：全ての駒を、原点を中心に反時計回りに 90 度回転させた位置に移動する
  • 3 p：全ての駒を、直線 x=p について対称な位置に移動する
  • 4 p：全ての駒を、直線 y=p について対称な位置に移動する

クエリが Q 個与えられます。 i 番目のクエリでは 2 つの整数 A_i,B_i が与えられるので、A_i 個目の操作を行った直後に駒 B_i がある座標を出力してください。ここで、1 個目の操作の直前を「0 個目の操作の直後」とみなします。

制約

  • 入力は全て整数
  • 1 \leq N \leq 2\times 10^5
  • 1 \leq M \leq 2\times 10^5
  • 1 \leq Q \leq 2\times 10^5
  • -10^9 \leq X_i,Y_i \leq 10^9
  • \mathrm{op}_i は 4 つの操作の種類のいずれかの入力形式に従う
  • 3 p 及び 4 p の操作において -10^9 \leq p \leq 10^9
  • 0 \leq A_i \leq M
  • 1 \leq B_i \leq N

入力

入力は以下の形式で標準入力から与えられる。

N
X_1 Y_1
\vdots
X_N Y_N
M
\mathrm{op}_1
\vdots
\mathrm{op}_M
Q
A_1 B_1
\vdots
A_Q B_Q

出力

各クエリに対する答えを、1 行に 1 つずつ、x 座標、y 座標の順に空白区切りで出力せよ。

入力例 1

1
1 2
4
1
3 3
2
4 2
5
0 1
1 1
2 1
3 1
4 1

出力例 1

1 2
2 -1
4 -1
1 4
1 0

最初、唯一の駒である駒 1 は (1,2) に置かれています。各操作により駒 1 の位置は (1,2)\to(2,-1)\to(4,-1)\to(1,4)\to(1,0) と変化します。

入力例 2

2
1000000000 0
0 1000000000
4
3 -1000000000
4 -1000000000
3 1000000000
4 1000000000
2
4 1
4 2

出力例 2

5000000000 4000000000
4000000000 5000000000

Score : 500 points

Problem Statement

There are N pieces on a two-dimensional plane. The coordinates of Piece i are (X_i,Y_i). There may be multiple pieces at the same coordinates.

We will do M operations \mathrm{op}_1, \ldots, \mathrm{op}_M, one by one. There are four kinds of operations, described below along with their formats in input.

  • 1：Rotate every piece 90 degrees clockwise about the origin;
  • 2：Rotate every piece 90 degrees counterclockwise about the origin;
  • 3 p：Move each piece to the point symmetric to it about the line x=p;
  • 4 p：Move each piece to the point symmetric to it about the line y=p.

You are given Q queries. In the i-th query, given two integers A_i and B_i, print the coordinates of Piece B_i just after the A_i-th operation. Here, the moment just before the 1-st operation is considered to be the moment just after "the 0-th operation".

Constraints

  • All values in input are integers.
  • 1 \leq N \leq 2\times 10^5
  • 1 \leq M \leq 2\times 10^5
  • 1 \leq Q \leq 2\times 10^5
  • -10^9 \leq X_i,Y_i \leq 10^9
  • \mathrm{op}_i is in the format of one of the four kinds of operations.
  • In an operation with the form 3 p or 4 p, -10^9 \leq p \leq 10^9.
  • 0 \leq A_i \leq M
  • 1 \leq B_i \leq N

Input

Input is given from Standard Input in the following format:

N
X_1 Y_1
\vdots
X_N Y_N
M
\mathrm{op}_1
\vdots
\mathrm{op}_M
Q
A_1 B_1
\vdots
A_Q B_Q

Output

Print the response to each query in its own line: the x- and y-coordinates, in this order, with space in between.

Sample Input 1

1
1 2
4
1
3 3
2
4 2
5
0 1
1 1
2 1
3 1
4 1

Sample Output 1

1 2
2 -1
4 -1
1 4
1 0

Initially, the only piece - Piece 1 - is at (1, 2). Each operation moves the piece as follows: (1,2)\to(2,-1)\to(4,-1)\to(1,4)\to(1,0).

Sample Input 2

2
1000000000 0
0 1000000000
4
3 -1000000000
4 -1000000000
3 1000000000
4 1000000000
2
4 1
4 2

Sample Output 2

5000000000 4000000000
4000000000 5000000000