첫 번째 큰 수

난이도: Platinum II 출제자: rlatjwls7882 시간 제한: 1000 ms 메모리 제한: 512 MB

제곱근 분할법

길이가 $N$인 수열 $A$가 있다. $Q$개의 쿼리를 순서대로 처리하라.

쿼리는 다음 중 하나이다.

1 i x: $A_i$를 $x$로 바꾼다. $(1 \leq i \leq N,\ -10^9 \leq x \leq 10^9)$
2 l r x: $l \leq i \leq r$이면서 $A_i \geq x$인 가장 작은 $i$를 출력한다. 조건을 만족하는 $i$가 없다면 -1을 출력한다. $(1 \leq l \leq r \leq N,\ -10^9 \leq x \leq 10^9)$

입력

첫 번째 줄에 수열의 길이 $N$과 쿼리의 개수 $Q$가 주어진다. $(1 \leq N,Q \leq 200\,000)$

두 번째 줄에 수열의 원소 $A_1,A_2,\ldots,A_N$이 주어진다. $(-10^9 \leq A_i \leq 10^9)$

세 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 하나씩 주어진다.

2 l r x 쿼리마다 조건을 만족하는 가장 작은 인덱스를 한 줄에 하나씩 출력한다.

6 7
1 5 2 8 3 7
2 1 6 6
2 2 5 9
1 3 10
2 2 5 9
1 4 -1
2 1 6 6
2 4 6 6