B - Group Moving
問題文
$N \times N$ のマス目があり、$M$ 頭のゴリラがいます。
$i\space(1\leq i \leq M)$ 番目のゴリラは、$(A_i, B_i)$ のマス目にいて、$C_i$ 色のネクタイをつけています。
(上から $x\space (1 \leq x \leq N)$ 行目、左から $y\space (1 \leq y \leq N)$ 列目のマスを $(x,y)$ と表現しています。)
ここから $Q$ 回の移動を行います。
$i\space (1 \leq i \leq Q)$ 番目の移動では、$K_i$ 色のネクタイをつけたゴリラ全員が、今いるマス目から下に $X_i$ 、右に $Y_i$ の位置に移動します。
ただし、マス目はトーラス状であるとみなします。
すなわち、各 $1\leq i \leq N$ に対してマス $(i,N)$ の右にマス $(i,1)$ があり、各 $1\leq j \leq N$ に対してマス $(N,j)$ の下にマス $(1,j)$ があるとします。
$M$ 頭それぞれについて、$Q$ 回の移動が終わった時点にいるマスの位置を出力してください。
なお、複数頭が同じマスにいることもあります。
制約
- 入力は全て整数
- $2 \leq N \leq 2 \times 10^5$
- $1 \leq M \leq 2 \times 10^5$
- $1 \leq A_i, B_i \leq N$
- $1 \leq C_i \leq 10^9$
- $1 \leq Q \leq 2 \times 10^5$
- $1 \leq K_i \leq 10^9$
- $ |X_i|, |Y_i| \leq N-1$
入力
入力は以下の形式で標準入力から与えられます。
$N$ $M$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$\cdots$
$A_M$ $B_M$ $C_M$
$Q$
$K_1$ $X_1$ $Y_1$
$K_2$ $X_2$ $Y_2$
$\cdots$
$K_Q$ $X_Q$ $Y_Q$
出力
移動後の $i\space (1 \leq i \leq M)$ 番目のゴリラの位置を $(p_i, q_i)$ として、$M$ 行出力して下さい。
$p_1$ $q_1$
$p_2$ $q_2$
$\cdots$
$p_M$ $q_M$
3 3
1 1 10
1 3 20
3 2 20
3
10 1 1
20 1 1
10 0 -1
2 1
2 1
1 3
-
初期状態では、$1$ 番目のゴリラは $(1,1)$ に、$2$ 番目のゴリラは $(1,3)$ に、$3$ 番目のゴリラは $(3,2)$ にいます。
-
$1$ 回目の移動では、色 $10$ のネクタイをつけた $1$ 番目のゴリラが、下に $1$、右に $1$ 移動します。
- その結果 $(1,1)$ → $(2,2)$ に移動します。
-
$2$ 回目の移動では、色 $20$ のネクタイをつけた $2,3$ 番目のゴリラが、下に $1$、右に $1$ 移動します。
-
その結果それぞれ $(1,3)$ → $(2,1)$、$(3,2)$ → $(1,3)$ に移動します。
-
$N$ 行目と $1$ 行目、$N$ 列目と $1$ 列目がそれぞれ隣接していることに注意してください。
-
-
$3$ 回目の移動では、色 $10$ のネクタイをつけた $1$ 番目のゴリラが、下に $0$、右に $-1$ 移動します。
-
その結果 $(2,2)$ → $(2,1)$ に移動します。
-
右に負の距離 $d$ 移動するとは、左に $-d$ 移動することを指します。上下についても同様です。
-
初期状態、移動の過程・結果において、同じマスに複数のゴリラがいることもあります。
10 10
1 8 127644670
5 2 855839114
8 7 266622740
7 8 416441111
7 1 186242600
3 7 337534189
7 5 272435243
10 4 119871314
7 10 506901437
4 9 87702648
10
506901437 -6 -8
127644670 -4 -6
416441111 5 -1
119871314 8 8
119871314 3 -4
127644670 -1 -1
127644670 2 3
337534189 8 -8
337534189 -5 4
20240928 9 -9
8 4
5 2
8 7
2 7
7 1
6 3
7 5
1 8
1 2
4 9
$10$ 番目のクエリのように、誰もつけていないネクタイの色が指示されることもあります。このときは誰も移動しません。