Historical Maximum Query

You are given a sequence \(a_1, a_2, \dots, a_n\) and you need to process \(m\) operations. There are two types of operations:

• Modification operation: Given three integers \(l, r, x\), add \(x\) to each element in the segment \(a_l, a_{l+1}, \dots, a_r\). When an element is modified, its historical maximum is updated if its new value is greater than the previous maximum. The historical maximum of an element is defined as the highest value it has ever taken (including its initial value).
• Query operation: Given three integers \(l, r, x\), among those indices \(i\) where \(l \le i \le r\) and the current value \(a_i < x\), output the maximum historical value of \(a_i\). If no element in the given range satisfies \(a_i < x\), output \(-1\).

The operations are given in sequential order. Input operations will be in one of the following two forms:

1 l r x   // Modification: add x to all a[i] for i from l to r
2 l r x   // Query: output the maximum historical value of a[i] for i from l to r such that a[i] < x

Answer each query in the order they appear.

inputFormat

The first line contains two integers \(n\) and \(m\) separated by a space, where \(n\) is the length of the sequence and \(m\) is the number of operations.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) which represent the initial values of the sequence.

The following \(m\) lines describe the operations. Each operation is given in the format:

op l r x

Here, op is either 1 (modification) or 2 (query), and \(l, r, x\) are integers.

outputFormat

For each query operation, output the answer on a new line. The answer is the maximum historical value among all \(a_i\) (for \(l \le i \le r\)) satisfying \(a_i < x\), or \(-1\) if no such element exists.

sample

5 5
1 2 3 4 5
2 2 4 5
1 1 3 2
2 1 5 5
1 2 5 1
2 3 5 7

4
4
6