You are given an array \(A\) of size \(N\). You have to perform \(Q\) queries on the array. Each of these queries belongs to the following types of queries:

\(L\) \(R\) \(X\) : Add \(X\) to all elements in the range \([L, R]\)
\(L\) \(R\) \(X\) : Set the value of all elements in the range \([L, R]\) to \(X\)

However, it is not mandatory to perform the queries in order. Your task is to determine the lexicographically largest array that can be obtained by performing all the \(Q\) queries.

Note:

The queries cannot be changed or skipped. You can only change the order in which they are performed.
If there exists an index \(i\) such than \(A_i > B_i\) and \(A_j = B_j\) for all \(1 \le j < i\), then the array \(A\) is lexicographically larger than an array \(B\).

Input format

First line: Two space-separated integers \(N\) and \(Q\)
Next line: \(N\) space-separated integers denoting the array \(A\)
Next \(Q\) lines: The queries to be performed of the \(type\) \(L\) \(R\) \(X\)

Output format

Print \(N\) space-separated integers that denote the lexicographically largest array that can be obtained as mentioned in the problem statement.

Constraints

\(1 \le N \le 500\)

\(1 \le Q \le 10^5\)

\(type \in \{1, 2\}\)

\(1 \le L \le R \le N\)

\(-10^5 \le X, A_i \le 10^5\)