# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

## 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** **(1 ≤ L ≤ R ≤ N)**. 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 **10 ^{9}+7**.

#### Input

The first line contains single integer **N (1 ≤ N ≤ 10 ^{5})**.

The second line contains **N** positive integers **A _{1} , A_{2} , … … … , A_{N} (1 ≤ A_{i} ≤ 10^{4})** .

The third line contains a single integer **M (1 ≤ M ≤ 10 ^{5})**.

Each of the next **M** lines contains 3 integers **L , R (1 ≤ L ≤ R ≤ N)** and **K ( 1 ≤ K ≤ 10 ^{15})**.

#### Output

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

#### Samples

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**.

Login to submit