You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 2.0 s

Memory Limit: 512.0 MB

Description

Thakur and Roy are playing a game with an array of length \(N\).

The game is played in turns, in each of their turn :

• the current player divides the array into two parts \([1\) to \(n/2]\) and \([(n/2)+1\) to \(n]\)
• then the current player erase one part of the array.

The game ends when the length of the array is 1.
Thakur wants to minimize the last remaining element and Roy wants to maximize the last reamining element.
You have to answer \(Q\) queries in form :

• \(i\) \(v\) \(p\) : replace the \(i^{th}\) index with the value \(v\) and then find the result of the game, assume that if \(p=0\) then Thakur takes the first move and if \(p=1\) then Roy takes the first move.

note : you have to assume that both Thakur and Roy plays optimally in their turn.

Input

first line takes two integer \(N,Q\) : size of the array and number of queries
next line takes \(N\) integers \(A_1,A_2,A_3....A_N\)
next \(Q\) line takes a query of the form mentioned above.

\(1 <= N,Q <= 2*10^5\)
\(1 <= A_i,v <= 10^9\)
\(p ∈ {{0,1}}\)
\(1 <= i <= N\)

Output

print one integer for each query in a new line

Sample

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

2
3
4
3