You come home and fell some unpleasant smell. Where is it coming from?

You are given an array $*a*$. You have to answer the following queries:

1. You are given two integers $*l*$ and $*r*$. Let $*c*_{*i*}$ be the number of occurrences of $*i*$ in $*a*_{*l*: *r*}$, where $*a*_{*l*: *r*}$ is the subarray of $*a*$ from $*l*$-th element to $*r*$-th inclusive. Find the Mex of ${*c*_{0}, *c*_{1}, ..., *c*_{10^{9}}}$
2. You are given two integers $*p*$ to $*x*$. Change $*a*_{*p*}$ to $*x*$.

The Mex of a multiset of numbers is the smallest non-negative integer not in the set.

Note that in this problem all elements of $*a*$ are positive, which means that $*c*_{0}$ = 0 and $0$ is never the answer for the query of the second type.

Input

The first line of input contains two integers $*n*$ and $*q*$ ($1 ≤ *n*, *q* ≤ 100 000$) — the length of the array and the number of queries respectively.

The second line of input contains $*n*$ integers — $*a*_{1}$, $*a*_{2}$, $...$, $*a*_{*n*}$ ($1 ≤ *a*_{*i*} ≤ 10^{9}$).

Each of the next $*q*$ lines describes a single query.

The first type of query is described by three integers $*t*_{*i*} = 1$, $*l*_{*i*}$, $*r*_{*i*}$, where $1 ≤ *l*_{*i*} ≤ *r*_{*i*} ≤ *n*$ — the bounds of the subarray.

The second type of query is described by three integers $*t*_{*i*} = 2$, $*p*_{*i*}$, $*x*_{*i*}$, where $1 ≤ *p*_{*i*} ≤ *n*$ is the index of the element, which must be changed and $1 ≤ *x*_{*i*} ≤ 10^{9}$ is the new value.

Output

For each query of the first type output a single integer  — the Mex of ${*c*_{0}, *c*_{1}, ..., *c*_{10^{9}}}$.

Note

The subarray of the first query consists of the single element — $1$.

The subarray of the second query consists of four $2$s, one $3$ and two $1$s.

The subarray of the fourth query consists of three $1$s, three $2$s and one $3$.