Advanced Imos

2 secs 1024 MB
take44444's icon take44444

問題

長さNNの数列AA (a1,a2,,aN)(a_1,a_2,…,a_N)が与えられます.QQ個のクエリを処理した後の数列AAを求めてください.

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

i=L,L+1,,Ni=L,L+1,…,Nについて,aia_i(X×ai+Y)mod1000000007(X \times a_i + Y) \mod 1000000007に置き換える.

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

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

制約

  • 1N,Q1071 \leq N, Q \leq 10^7
  • 1ai,X,Y1091 \leq a_i, X, Y \leq 10^9
  • 1LiN(1iQ)1 \leq L_i \leq N (1 \leq i \leq Q)
  • LiLj(1i<jQ)L_i \leq L_j (1 \leq i < j \leq Q)
  • 入力は全て整数

入力

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

Submit


Go (1.21)