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.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class F {

    private static class Query1 {
        private int i, update, l, r;

        Query1(int i, int update, int l, int r) {
            this.i = i;
            this.update = update;
            this.l = l;
            this.r = r;
        }
    }

    private static class Query2 {
        private int pos, next, prev;

        Query2(int pos, int next, int prev) {
            this.pos = pos;
            this.next = next;
            this.prev = prev;
        }
    }

    private static int n, q;
    private static int[] a = new int[123456];

    private static List<Query1> queries1 = new ArrayList<>();
    private static ArrayList<Query2> queries2 = new ArrayList<>();

    private static Map<Integer, Integer> replacement = new HashMap<>();

    private static int replace(int x) {
        if (replacement.containsKey(x))
            return replacement.get(x);
        replacement.put(x, replacement.size());
        return replacement.size() - 1;
    }

    private static int[] f = new int[234567];
    private static int[] ff = new int[234567];

    private static void plus(int x) {
        ff[f[x]]--;
        ff[++f[x]]++;
    }

    private static void minus(int x) {
        ff[f[x]--]--;
        ff[f[x]]++;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] splits;
        PrintWriter out = new PrintWriter(System.out, true);

        splits = in.readLine().split(" ");
        n = Integer.parseInt(splits[0]);
        q = Integer.parseInt(splits[1]);

        splits = in.readLine().split(" ");
        for (int i = 0; i < n; i++)
            a[i] = replace(Integer.parseInt(splits[i]));

        int[] tmp = Arrays.copyOf(a, n);
        for (int i = 0; i < q; i++) {
            splits = in.readLine().split(" ");
            if (splits[0].charAt(0) == '1') {
                queries1.add(
                    new Query1(
                        queries1.size(),
                        queries2.size() - 1, Integer.parseInt(splits[1]) - 1, Integer.parseInt(splits[2]) - 1
                    )
                );
            } else {
                int pos = Integer.parseInt(splits[1]) - 1;
                int next = replace(Integer.parseInt(splits[2]));
                queries2.add(new Query2(pos, next, tmp[pos]));
                tmp[pos] = next;
            }
        }

        int blockLength = (int) Math.pow(n, 2./3.);
        Collections.sort(queries1, (q1, q2) -> {
            int cmp1 = (q1.update/blockLength) - (q2.update/blockLength);
            if (cmp1 == 0) {
                int cmp2 = (q1.l/blockLength) - (q2.l/blockLength);
                if (cmp2 == 0)
                    return q1.r - q2.r;
                return cmp2;
            }
            return cmp1;
        });

        int update = -1;
        int l = 0;
        int r = -1;
        int[] ans = new int[queries1.size()];

        for (Query1 q1 : queries1) {
            while (r < q1.r)
                plus(a[++r]);
            while (l > q1.l)
                plus(a[--l]);
            while (r > q1.r)
                minus(a[r--]);
            while (l < q1.l)
                minus(a[l++]);
            while (update < q1.update) {
                Query2 q2 = queries2.get(++update);
                if (l <= q2.pos && q2.pos <= r) {
                    minus(q2.prev);
                    plus(q2.next);
                }
                a[q2.pos] = q2.next;
            }
            while (update > q1.update) {
                Query2 q2 = queries2.get(update--);
                if (l <= q2.pos && q2.pos <= r) {
                    minus(q2.next);
                    plus(q2.prev);
                }
                a[q2.pos] = q2.prev;
            }

            for (int i = 1; ; i++) {
                if (ff[i] == 0) {
                    ans[q1.i] = i;
                    break;
                }
            }
        }

        for (int x : ans)
            out.println(x);
        out.flush();
    }

}