Given N boxes labelled 1 to N each box having non negative amount of chocolates. You are assigned with a task of distributing more chocolates in the boxes. You have infinite supply of chocolates.

You have been given Q queries. In each query you will be given three integers L, R and V. In each query you have to add V chocolates each, to all the boxes between L to R (L and R inclusive).

You have to calculate the final amount of chocolates in each box after processing all the queries.

Input

First line contains an integer N denoting the number of chocolate boxes.

Second line contains N non ngetaive integers denoting the number of chocolates in each box.

Third line contains Q denoting the number of queries.

Next Q lines contain L_i, R_i, V_i for each i^th query.

Output

Print the total amount of chocolates each box has after performing all the queries.

Constraints

$1\leq N \leq 10^6$

$1 \leq Q \leq 10^6$

$1\leq L, R, \leq N$

$1\leq V, BOX[i] \leq 10^6$

Author :Mohit Tarani