시간 제한메모리 제한제출정답맞힌 사람정답 비율
20 초 (추가 시간 없음) 512 MB222100.000%

문제

You are given an array $a$.

Process two types of queries:

  1. You are given $x$ and $y$. Set $a_x$ to $y$.
  2. You are given $l$, $r$ and $k$. Find the largest value of $m$, such that sequence $k, k+1, \ldots, m$ is a subsequence of $a_{l:r}$.

입력

The first line contains two integers $n$ and $q$ ($1 \leq n, q \leq 10^6$), the length of $a$ and the number of queries, respectively.

The second line contains $n$ integers $a_i$ ($0 \leq a_i < n$), the elements of $a$.

$q$ lines follow. Each of them has one of the following forms:

  • $1 x y$ ($0 \leq x, y < n$), describing a query of the first type.
  • $2 l r k$ ($0 \leq l < r \leq n$, $0 \leq k < n$), describing a query of the second type. Note that half-intervals are used, i.e. $a_{0:3}$ contains elements with indices $0$, $1$ and $2$. It is guaranteed that the given half-interval contains at least one element equal to $k$.

출력

For each query of the second type print the corresponding $m$.

예제 입력 1

6 17
0 0 0 1 2 1
2 0 4 0
2 0 5 0
1 3 2
2 0 4 0
2 0 6 0
2 0 4 2
2 5 6 1
1 0 1
2 1 6 1
2 0 5 1
1 0 0
1 5 5
1 2 2
1 4 4
1 3 3
1 1 1
2 0 6 0

예제 출력 1

1
2
0
1
2
1
1
2
5