Problem: 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 ci be the number of occurrences of i in al: r, where al: r is the subarray of a from l-th element to r-th inclusive. Find the Mex of {c0, c1, ..., c109}
  2. You are given two integers p to x. Change ap 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 c0 = 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 — a1, a2, ..., an (1 ≤ ai ≤ 109).

Each of the next q lines describes a single query.

The first type of query is described by three integers ti = 1, li, ri, where 1 ≤ li ≤ ri ≤ n — the bounds of the subarray.

The second type of query is described by three integers ti = 2, pi, xi, where 1 ≤ pi ≤ n is the index of the element, which must be changed and 1 ≤ xi ≤ 109 is the new value.

Output

For each query of the first type output a single integer — the Mex of {c0, c1, ..., c109}.

Example

Input

10 4
1 2 3 1 1 2 2 2 9 9
1 1 1
1 2 8
2 7 1
1 2 8


Output

2
3
2

Note

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

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

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

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;
import java.text.*;
public class Code{
    static final long MOD = (long)1e9+7;
    static FastReader in;
    
    static int N, Q, D, uc,qc, t, l,r;
    static int[] A, ans, f, ff;
    static int[][] u,q;
    public static void main(String[] args){
        in = new FastReader();
        N = ni(); Q = ni();
        A = new int[N+1];int[] tmp = new int[N+1];
        HashMap<Long, Integer> map = new HashMap<>();
        for(int i = 1; i<= N; i++){
            long x = nl();
            if(!map.containsKey(x))map.put(x, D++);
            A[i] = map.get(x);
            tmp[i] = A[i];
        }
        uc = 0;qc = 0;
        u = new int[Q][];q = new int[Q][];
        for(int i = 0; i< Q; i++){
            int t = ni();
            if(t==1){
                q[qc] = new int[]{qc, ni(), ni(),uc};
                qc++;
            }else{
                uc++;
                int p = ni();long x = nl();
                if(!map.containsKey(x))map.put(x,D++);
                u[uc] = new int[]{p, tmp[p], map.get(x)};
                tmp[p] = u[uc][2];
            }
        }
        int B = 2150;
        Arrays.sort(q,0,qc,new Comparator<int[]>(){
            public int compare(int[] i1, int[] i2){
                if(i1[1]/B != i2[1]/B)return Integer.compare(i1[1], i2[1]);
                if(i1[2]/B != i2[2]/B)return Integer.compare(i1[2], i2[2]);
                return Integer.compare(i1[3], i2[3]);
            }
        });
        ans = new int[qc];
        f = new int[D];ff = new int[N+1];
        t=0;l=1;r=0;
        for(int i = 0; i< qc; i++){
            while(t<q[i][3])update(true);
            while(t>q[i][3])update(false);
            while(r<q[i][2])move(++r,true);
            while(l>q[i][1])move(--l,true);
            while(r>q[i][2])move(r--,false);
            while(l<q[i][1])move(l++,false);
            ans[q[i][0]] = mex();
        }
        StringBuilder out = new StringBuilder("");
        for(int i:ans)out.append(i+"\n");
        System.out.print(out.toString());
    }
    
    static void update(boolean up){
        if(up)t++;
        int p = u[t][0], prev = 0, cur = 0;
        if(up){
            prev = u[t][1];
            cur = u[t][2];
        }else{
            prev = u[t][2];
            cur = u[t][1];
        }
        A[p] = cur;
        if(p>=l && p<=r){
            ff[f[prev]]--;
            ff[f[cur]]--;
            f[prev]--;
            f[cur]++;
            ff[f[prev]]++;
            ff[f[cur]]++;
        }
        if(!up)t--;
    }
    
    static void move(int p, boolean add){
        ff[f[A[p]]]--;
        if(add)f[A[p]]++;
        else f[A[p]]--;
        ff[f[A[p]]]++;
    }
    
    static int mex(){
        int x = 0;
        while(true)if(ff[++x]==0)return x;
    }
    
    static int gcd(int a,int b){
        return (b==0)?a:gcd(b,a%b);
    }
    
    static String n(){
        return in.next();
    }
    
    static String nln(){
        return in.nextLine();
    }
    
    static int ni(){
        return Integer.parseInt(in.next());
    }
    
    static long nl(){
        return Long.parseLong(in.next());
    }
    
    static double nd(){
        return Double.parseDouble(in.next());
    }
    
    static class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        
        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

 
        String next(){
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        String nextLine(){
            String str = "";
            try{
                str = br.readLine();
            }catch (IOException e){
                e.printStackTrace();
            }
            return str;
        }
    }
    
}