There are many ghosts at the abandoned station on unknown railway.
We mark the abandoned stations as 1,2..n according to the order. There are ai ghosts at the ith station.Yakumo Yukari often opens a black hole and makes a train appearing at a certain station. For example, the train appears at the x station, and k ghosts get off at the station. Then there would be k+d ghosts at the x+1 station to get off,k+2×d at x+2 station and so on....There would be k+y∗d ghosts at the x+y station to get off (0≤y,x+y≤n). In others words, the numbers getting off at x,x+1,x+2..n station form a tolerance of d arithmetic progression.(you can consider ghosts getting off at the same time.)Onozuka Komachi would comes a certain station to take away the ghosts.(The number of ghosts at the station would become 0)You have the records of trains appearing and Komachi coming. You should tell Komachi how much ghosts at a certain station when she come to there.
输入描述:
The first line contains an positive integer T(1≤T≤10), represents there are T test cases.
For each test case:
The first line contains three positive integers n,m,d(1≤n≤105,1≤m≤105,1≤d≤1000) - the number of station,the number of records,and the tolerance of the arithmetic progress.
The second line contains n integers a1,a2…an(1≤ai≤1000). Then m lines followed. Each line contains a records and there are two types. 1 x y,indicating train appearing at x station and y ghosts geting off. 2 x y,indicating Komachi coming to the x station. (1≤x≤n,0≤y≤1000)
输出描述:
For each second records(2 x), output an integer in one line, representing the number of ghosts at the station.Since the ans may be too large, out put tme ans mod 109+7.
示例1
输入
2
6 6 1
1 2 3 3 2 1
1 1 1
2 1
2 2
2 3
2 4
2 5
5 3 2
1 2 3 4 5
1 3 0
2 4
2 4
说明
There lists the number of ghosts changing at these station.
case1：
1 2 3 3 2 1
2 4 6 7 7 7
0 4 6 7 7 7
0 0 6 7 7 7
0 0 0 7 7 7
0 0 0 0 7 7
0 0 0 0 0 7
case2：
1 2 3 4 5
1 2 3 6 9
1 2 3 0 9
1 2 3 0 9
