問題
長さNの数列A (a1,a2,…,aN)が与えられます.Q個のクエリを処理した後の数列Aを求めてください.
各クエリではL, X, Yが与えられます.以下の処理をしてください.
i=L,L+1,…,Nについて,aiを(X×ai+Y)mod1000000007に置き換える.
ただし,各クエリにおいて,Lの値は,それ以前のクエリに含まれるLの最大値以上のものが与えられます.
Note: 各種セグメント木を使わずに解いてください.
制約
- 1≤N,Q≤107
- 1≤ai,X,Y≤109
- 1≤Li≤N(1≤i≤Q)
- Li≤Lj(1≤i<j≤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
出力
サンプル
入力例1
出力例1
入力例2
5 4
1 2 3 4 5
2 1 25
3 2 15
4 3 35
5 4 5
出力例2