You are given an array \(A\) having \(N\) integers. You take an array \(B\) of length \(N\) such that \(B_i = 0\) for all \(1 \le i \le N\). You perform \(Q\) operations of the following two types:

• \(1 \;L \;R\; X\) : add \(X\) to all elements of the subarray \(A[L \dots R]\)
• \(2 \; L\;R\) : add \(A_i\) to \(B_i\) for all \(L \le i \le R\).

Print the elements of the array \(B\) after \(Q\) operations.

  Input format

• The first line of input contains two integers \(N, Q\) denoting the length of the array \(A\) and the number of operations respectively.
• The second line contains \(N\) integers \(A_1, A_2,\dots, A_N\), denoting elements of the array \(A\).
• Each of the next \(Q\) lines contains a description of one of the two types of operations. 

Output format

Print \(N\) integers \(B_1, B_2,\dots, B_N\), denoting elements of the array \(B\) after \(Q\) operations.

Constraints

\(1 \leq N, Q \leq 2\cdot 10^5\\ 1\le A_i,X\le 10^5\\ 1 \le L_i \le R_i \le N\)