Description

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

You need to perform $m$ operations.

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

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

Input Format

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

Then follow $m$ lines, each with three integers $l\;r\;L$, representing a query.

Output Format

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

3
1 2 3
1
1 2 2

0
1
2

Hint

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

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

Translated by ChatGPT 5