Given two sequences $a_1, \dots, a_n$ and $b_1, \dots, b_n$, where initially $b_i = 0$.

You need to perform $m$ operations:

In each operation, you are given $l, r, L$. For each $k \in [l, r]$, you must add $a_k$ to $b_{L+k-l}$.

Finally, output the sequence $b_1, \dots, b_n$ after all operations.

Input

The first line contains an integer $n$.

The second line contains $n$ integers $a_1, \dots, a_n$.

The third line contains an integer $m$.

The following $m$ lines each contain three integers $l, r, L$, representing an operation.

Output

Output $n$ lines, representing the sequence $b_1, \dots, b_n$ after the operations.

Examples

Input 1

3
1 2 3
1
1 2 2

Output 1

0
1
2

Subtasks

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078

For $100\%$ of the data, $0 \le a_i \le 1000$, $1 \le n \le 10^5$, and $1 \le m \le 10^6$.