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\)
In this case, the order in which the queries are performed does not matter. Assuming the queries are performed in the same order as the input, the array after each query is as follows:
Initially, \([ 1, 2, 3, 4, 5 ]\)
After query 1, \([1, 2, 5, 6, 5]\)
After query 2, \([3, 3, 5, 6, 5]\)
After query 3, \([3, 3, 5, 0, -1]\)
Observe that the final array would have been same even if the queries were performed in some other order.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor