Recover Lost Parameters

Little E faced a classic problem. He was given a sequence (a) of length (n) and (q) operations. There are two types of operations:

1. (\tt{1~l~r~x}): For every index (i) such that (l \le i \le r), update (a_i \leftarrow a_i+x).
2. (\tt{2~l~r~x}): For every index (i) such that (l \le i \le r), update (a_i \leftarrow \max(a_i, x)).

After performing all operations in order, the final sequence (a') is output. However, because of a cosmic ray incident, the input data got corrupted: in every type 2 operation, the parameter (x) was lost – the operations are now given in the form (\tt{2~l~r}) only. The output (the final sequence) is correct.

Your task is to help Little E recover a possible original input (i.e. fill in a valid (x) for every type 2 operation) such that when the operations are applied on the given initial sequence, the final sequence becomes exactly (a'). If there are multiple valid answers, you may output any one of them. It is guaranteed that at least one solution exists.

Input Format

• The first line contains two integers \(n\) and \(q\) --- the length of the sequence and the number of operations.
• The second line contains \(n\) integers, representing the initial sequence \(a\).
• The next \(q\) lines each describe an operation. For a type 1 operation, the line contains four numbers: `1 l r x`. For a type 2 operation, due to corruption, the line contains only three numbers: `2 l r`.
• The last line contains \(n\) integers, representing the final sequence \(a'\).

Output Format

• Output the recovered original input data in the same format as above. For each type 2 operation, you must output one valid integer \(x\) such that if we simulate the operations on the initial sequence, we obtain the final sequence \(a'\).

Problem Note

You may assume that the recovered input is not unique; any valid reconstruction is acceptable. It is guaranteed that a solution exists.

Example

Consider the following recovered input:

5 3
0 0 0 3 3
1 1 3 5
2 2 5 3
1 4 5 2
5 5 5 5 5

Explanation:

• Initial sequence: \([0, 0, 0, 3, 3]\)
• Operation 1: Add 5 to indices 1 through 3: sequence becomes \([5, 5, 5, 3, 3]\)
• Operation 2: For indices 2 through 5, replace each element with \(\max(a_i,3)\). The sequence stays \([5, 5, 5, 3, 3]\) because the values are already at least 3.
• Operation 3: Add 2 to indices 4 and 5, making the final sequence \([5, 5, 5, 5, 5]\).

---

Approach: One viable strategy to solve the recovery is to work backwards. Let the final array be \(F=a'\). Process the operations in reverse order: for a type 1 operation, subtract \(x\) from the affected segment; for a type 2 operation (with missing \(x\)), choose \(x' = \min_{l \le i \le r}(F[i])\) and assume that before the operation the segment was such that applying \(\max(\cdot, x')\) resulted in the current values. This backward simulation recovers a valid initial sequence and also the missing parameters. Then simply output the recovered input data in the original order.

inputFormat

The input begins with two integers \(n\) and \(q\). The second line contains \(n\) integers denoting the initial sequence \(a\). The next \(q\) lines describe operations. A line starting with 1 is a type 1 operation in the format: 1 l r x. A line starting with 2 is a type 2 operation in the format: 2 l r (note that the parameter \(x\) is missing due to corruption). The final line contains \(n\) integers representing the final sequence \(a'\).

outputFormat

Output the recovered original input data. The format should exactly match the input format: first the integers \(n\) and \(q\), then the initial sequence, followed by \(q\) operations (for type 2 operations, include the recovered \(x\) as the fourth number), and finally the final sequence \(a'\).

sample

5 3
0 0 0 0 0
1 1 3 5
2 2 5
1 4 5 2
5 5 5 5 5

5 3
0 0 0 3 3
1 1 3 5
2 2 5 3
1 4 5 2
5 5 5 5 5