Binary Search on Segment Tree

Problem Description

You are given $n$ numbers $a_1, a_2, a_3, \dots, a_n$.

You must support $q$ operations:

1. 1 x d: set $a_x = d$.
2. 2 l r d: among $a_l, a_{l+1}, a_{l+2}, \dots, a_r$, find the index of the first element that is $\ge d$; if no such element exists, output $-1$. In other words, find the smallest $i$ ($l \le i \le r$) such that $a_i \ge d$.

Input Format

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 2 \times 10^5$).

The next line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$).

The following $q$ lines each describe an operation of the form 1 x d or 2 l r d, with $1 \le x \le n$, $1 \le l \le r \le n$, and $1 \le d \le 10^9$.

Output Format

For each query, output one line containing the answer.

Sample Input

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

Sample Output

5
3
-1

Constraints

$1 \le n, q \le 2 \times 10^5$, $1 \le a_i, d \le 10^9$, $1 \le x \le n$, $1 \le l \le r \le n$.