Itachi's Challenge

Sasuke is a 12-year old ninja who is very much interested in learning Ninjutsu (A tactic used by ninjas). To learn new jutsu, he went to his older brother Itachi who is a very skilled ninja. But Itachi will teach him in one condition. Sasuke has to complete the following tasks.

Itachi will give Sasuke an array of N positive integers. There is a type of update operation called "Sub-array Sum Addition" or "SSA" in short.
In this update operation, he will be given two positions L and R. Let S be the sum of all the elements from position L to R. Then S will be added to all the elements in the range [L,R].

Now Itachi will give M commands to Sasuke. Sasuke will sequentially perform these commands on the given array. In each command, Itachi gives him three positive integers L , R and K. Sasuke will perform "SSA" update on the sub-array in range [L,R] exactly K times. The array gets modified after each "SSA" update.

After performing all the updates, Sasuke has to give him the whole array. As the elements can be huge, print them modulo 109+7.

Input

The first line contains single integer N (1 ≤ N ≤ 105).

The second line contains N positive integers A1, A2, ... ... , AN (1 ≤ Ai ≤ 104) .

The third line contains a single integer M (1 ≤ M ≤ 105).

Each of the next M lines contains 3 integers L , R (1 ≤ L ≤ R ≤ N) and K (1 ≤ K ≤ 1015).

Output

After performing all the updates, print the value of N integers of the array in a single line separated by spaces.

Sample

Input	Output
4 1 3 2 5 2 2 3 1 1 4 2	127 134 133 131
In the first command, S = 5. So the array elements become 1 8 7 5. In the second command, we have to apply SSA two times in the sub-array. At first, S = 21. Thus, the array elements become 22 29 28 26. Next, S = 105. Hence, the elements become 127 134 133 131.