問題


長さの数列 が与えられます.個のクエリを処理した後の数列を求めてください.

各クエリでは, , が与えられます.以下の処理をしてください.

について,に置き換える.

ただし,各クエリにおいて,の値は,それ以前のクエリに含まれるLの最大値以上のものが与えられます.

Note: 各種セグメント木を使わずに解いてください.

制約


  • 入力は全て整数

入力


N Q
a_1 a_2 ... a_N
L_1 X_1 Y_1
L_2 X_2 Y_2
...
L_Q X_Q Y_Q

出力


a_1 a_2 ... a_N

サンプル


入力例1


5 1
1 2 3 4 5
3 2 10

出力例1


1 2 16 18 20

入力例2


5 4
1 2 3 4 5
2 1 25
3 2 15
4 3 35
5 4 5

出力例2


1 27 71 254 1045

提出


Go (1.14)