One day Mehak and Meenal were having a fight between them To resolve the dispute a question was given to both of them.

Given an array of length N with elements A1 , A2, .... , An in it. M operations are needed to be performed on it. In each operation add K to each element present in the index-range of I to J (both inclusive). After performing all operations print all the elements of updated array.

One who solves the question first will be awarded. Since Meenal is good in programming therefore Mehak needs your help.

Input Format

First Line of program contains single integer N. Next line contains N integers separated with a space depicting the array. Next line contains single integer M. Next M lines contains three integers I, J and K respectively separated by a space.

Output Format

Output N integers of updated array in separate lines.

Constraints :

1 <= N <= 106

0 <= Ai <= 109

1 <= M <= 106

1 <= I <= J <= N

0 <= K <= 109

Warning : Large Input Output file. Use fast I/O.