005 - Robot Movement History

時間制限 2 秒 / メモリ制限 128 MB / 得点 500 / x 14 /

TLE
2sec
MLE
128MB
得点
500

問題

$H$ 階建てのビルに $N$ 台のロボットが配置されている。
$i$ $(1 \leq i \leq N)$ 台目のロボットは $f_i$ 階に配置されており、同じ階に複数のロボットが配置されていることはない。
これらのロボットは、とある管理会社にあるコンピュータによって制御されている。普段はどのロボットがどの階にいるかきちんと記録されているのだが、その記録が何者かによって消されてしまったようだ。
幸いにもロボットに送った命令のログは残っていたので命令のログから各ロボットがどの階にいるかを調べることにした。
$Q$ 回の命令のログが与えられるので、すべての命令が行われた後に各ロボットがどの階にいるかを出力せよ。

$j$ $(1 \leq j \leq Q)$ 回目の命令のログには $k_j,d_j,r_j$ の $3$ つの整数が書かれており、ロボットは以下のルールに従って移動する。

  • $d_j$ の値に応じて上の階、又は下の階へと移動する。
    • $d_j = 1$ ならば $k_j$ 台目のロボットが $1$ つ上の階へ移動する。
      ただし、$k_j$ 台目のロボットが $H$ 階にいる場合はその場に留まる。
    • $d_j = 0$ ならば $k_j$ 台目のロボットが $1$ つ下の階へと移動する。
      ただし、$k_j$ 台目のロボットが $1$ 階にいる場合はその場に留まる。
  • 移動先の階に別のロボットがいた場合、それらのロボットは今後同じように移動するようになる。
    例として、$2$ 台のロボット $x,y$ が同じ階にいる場合、$x$ が $1$ つ上の階へ移動すれば $y$ も $1$ つ上の階へ移動し、$y$ が $1$ つ下の階へ移動すれば $x$ も $1$ つ下の階へ移動するということである。
  • 以上のような移動が $r_j$ 回繰り返される。

入力

入力は以下の形式で標準入力から与えられる。 
$N$ $H$ $Q$
$f_1$ $f_2$ $\ldots$ $f_N$
$k_1$ $d_1$ $r_1$
$k_2$ $d_2$ $r_2$
$\vdots$
$k_Q$ $d_Q$ $r_Q$

出力

$Q$ 回の命令が行われた後に各ロボットがどの階にいるかを出力せよ。
出力は $N$ 行からなり、$i$ 行目には $i$ 台目のロボットがどの階にいるか、階の番号を整数で出力する。
出力の末尾には改行を入れること。

制約

  • $1 \leq N \leq 10^5$
  • $N \leq H \leq 10^9$
  • $1 \leq Q \leq 10^5$
  • $1 \leq f_i \leq H$
  • $f_i$ は互いに相異なる。
  • $1 \leq k_j \leq N$
  • $0 \leq d_j \leq 1$
  • $1 \leq r_j \leq H$
  • 入力は全て整数である。

入出力例

入力例１

5 10 3
1 5 10 8 4
5 0 2
3 0 4
4 1 8

出力例１

1
5
10
10
2

  • $1$ 回目の命令では、$5$ 台目のロボットが $2$ つ下の階($2$階)へと移動する。
  • $2$ 回目の命令では、$3$ 台目のロボットが $4$ つ下の階へと移動するが、$2$ 回目の移動で $4$ 台目のロボットと同じ階に移動するため、$4$ 台目のロボットは $3$ 台目のロボットと同じように移動するようになり、この $2$ 台のロボットは共に $6$ 階へと移動する。
  • $3$ 回目の命令では、$4$ 台目のロボットが $8$ つ上の階へと移動するが、$4$ 回目の移動で $10$ 階へと移動するため、それ以降の移動は行われずにそのまま $10$ 階に留まる。
    また、$3$ 台目のロボットと $4$ 台目のロボットは同じように移動するため、$3$ 台目のロボットも $4$ 台目のロボットと同様に $10$ 階へと移動する。

入力例２

5 10 1
3 10 8 2 6
2 0 9

出力例２

1
1
1
1
1

  • $2$ 台目のロボットは、$2$ 回目の移動で $3$ 台目のロボット、$4$ 回目の移動で $5$ 台目のロボット、$7$ 回目の移動で $1$ 台目のロボット、$9$ 回目の移動で $4$ 台目のロボットがいる階へと移動するため、すべてのロボットが $1$ 階へと移動する。

入力例３

15 500 20
55 26 442 274 410 219 112 441 94 178 15 40 141 282 213
8 0 54
1 0 36
15 0 34
7 0 59
15 1 94
6 1 28
9 0 27
1 1 100
12 0 64
7 1 92
8 1 40
14 1 40
13 1 7
9 0 83
8 1 9
12 1 9
7 1 74
8 0 75
11 1 68
15 0 36

出力例３

154
154
442
305
361
305
154
361
154
178
83
154
154
305
305