23709번 - Gleb Evstropov 다국어

문제

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

제한

힌트