Segment Tree

Source: AtCoder

Version: Phuoc Hung OJ Extended

Problem Statement

You are given an array $A_1,A_2,\ldots,A_N$. Process $Q$ queries:

• 1 X V: set $A_X=V$.
• 2 L R: print $\max(A_L,A_{L+1},\ldots,A_R)$.
• 3 X V: find the smallest index $j$ such that $X\le j\le N$ and $A_j\ge V$. If no such index exists, print $N+1$.

Input

The first line contains $N,Q$.

The second line contains $A_1,A_2,\ldots,A_N$.

The next $Q$ lines contain the queries.

Output

Print the answer for every query of type 2 or 3.

Subtasks

• Subtask 1 — 20%: $1\le N,Q\le50$.
• Subtask 2 — 30%: $1\le N,Q\le5000$.
• Subtask 3 — 50%: $1\le N,Q\le2\cdot10^5$, $0\le A_i,V\le10^9$.

Examples

Input

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

Output

3
3
2
6

Explanation

The sample is processed in order; every printed item/line corresponds to an operation that requires output.