Maximize Minimum Value After Cancellation Game

You are given a sequence a of length n and you need to process q queries. There are two types of queries:

• Game Query: 1 l r p q. In this query, consider the subarray a[l...r] (1-indexed) and only the numbers in the value range [p, q]. You can choose any value x that appears at least twice in this subarray and perform a cancellation operation on x as follows:</p>
  • Remove two occurrences of x from the entire sequence.
  • For every number v such that v < x, remove exactly one occurrence of v from the entire sequence (if it exists).

  The game stops immediately after one cancellation operation. Your goal is to choose a valid cancellation (if one exists) in order to maximize the minimum value among the remaining numbers in the sequence. However, if no valid cancellation exists (that is, the game cannot stop) or if there is any cancellation that would eliminate the entire sequence, output -1.

• Update Query: 2 i x. This query changes the value at position i (1-indexed) of the sequence to x.

Input Format:

1. The first line contains two integers n and q.
2. The next line contains n integers representing the sequence a.
3. Each of the following q lines is either a game query of the form 1 l r p q or an update query of the form 2 i x.

Output Format:

For each game query, output a single line containing the maximum possible minimum value among the remaining numbers after performing exactly one cancellation operation. If the game cannot stop or if there exists a cancellation that eliminates the entire sequence, output -1.

Note: All formulas are given in LaTeX format. For example, the value range is given by \([p,q]\) and the cancellation value by \(x\).

inputFormat

The first line contains two integers n and q (1 ≤ n, q ≤ 10⁵).

The second line contains n integers: a1, a2, …, an.

Each of the next q lines represents a query and is either in the form:

• 1 l r p q (game query), or
• 2 i x (update query).

All indices are 1-indexed.

outputFormat

For each game query, output one line containing a single integer: the maximum possible minimum value among the remaining numbers after a cancellation operation, or -1 if the game cannot stop or a cancellation exists that eliminates the entire sequence.

sample

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

3
-1
3

</p>