Cây đoạn (Segment Tree)

Nguồn: AtCoder

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho dãy $A_1,A_2,\ldots,A_N$. Hãy xử lý $Q$ truy vấn:

• 1 X V: gán $A_X=V$.
• 2 L R: in $\max(A_L,A_{L+1},\ldots,A_R)$.
• 3 X V: tìm chỉ số nhỏ nhất $j$ thỏa $X\le j\le N$ và $A_j\ge V$. Nếu không tồn tại, in $N+1$.

Input

Dòng đầu chứa $N,Q$.

Dòng thứ hai chứa $A_1,A_2,\ldots,A_N$.

$Q$ dòng tiếp theo chứa các truy vấn.

Output

In đáp án của mỗi truy vấn loại 2 hoặc 3 trên một dòng.

Subtask

• 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$.

Ví dụ

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

Giải thích

Truy vấn loại 2 đầu lấy max toàn dãy bằng $3$. Truy vấn loại 3 từ vị trí $2$ với ngưỡng $3$ tìm được vị trí $3$. Sau cập nhật, các đáp án sau thay đổi tương ứng.