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:

//package codeTrainingLeetcode;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Scanner;

public class C466D2F {
	private static void addOrRemove(int[] g, int[] s, int ord, int y) {
		g[s[ord]]--;
		s[ord] += y;
		g[s[ord]]++;
	}

	private static int getAns(int[] a) {
		int i;
		for (i = 1; a[i] != 0; i++)
			;
		return i;
	}

	// Ī���㷨
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int q = scanner.nextInt();
		int blockSize = (int) Math.pow(n, 2.0 / 3);

		int[] a = new int[n + 1];
		int[] tmp = new int[n + 1];
		int count = 0;
		HashMap<Integer, Integer> hashMap = new HashMap<>();
		for (int i = 1; i <= n; i++) {
			a[i] = scanner.nextInt();
			if (hashMap.getOrDefault(a[i], 0) == 0)
				hashMap.put(a[i], ++count);
			a[i] = tmp[i] = hashMap.get(a[i]);
		}

		int quesNum = 0, changeNum = 0;
		int[][] quesInfo = new int[q + 1][];
		int[][] changeInfo = new int[q + 1][];
		for (int i = 1; i <= q; i++) {
			int tag = scanner.nextInt();
			if (tag == 1) {
				++quesNum;
				quesInfo[quesNum] = new int[] { quesNum, scanner.nextInt(), scanner.nextInt(), changeNum };
			} else {
				++changeNum;
				int idx = scanner.nextInt(), t = scanner.nextInt();
				if (hashMap.getOrDefault(t, 0) == 0)
					hashMap.put(t, ++count);
				int m = hashMap.get(t);
				changeInfo[changeNum] = new int[] { idx, m, tmp[idx] };
				tmp[idx] = m;
			}
		}

		Arrays.sort(quesInfo, 1, quesNum + 1, new Comparator<int[]>() {
			@Override
			public int compare(int[] a1, int[] a2) {
				int b1 = a1[1] / blockSize, b2 = a2[1] / blockSize;
				if (b1 == b2) {
					int sb1 = a1[2] / blockSize, sb2 = a2[2] / blockSize;
					if (sb1 == sb2) {
						return a1[3] - a2[3];
					}
					return sb1 - sb2;
				}
				return b1 - b2;
			}
		});

		int l = 1, r = 0, k = 0;
		int[] ordNumArr = new int[n << 1 + 2];
		int[] numArr = new int[n + 1];
		int[] ans = new int[quesNum + 1];
		for (int i = 1; i <= quesNum; i++) {
			while (l > quesInfo[i][1])
				addOrRemove(numArr, ordNumArr, a[--l], 1);
			while (r < quesInfo[i][2])
				addOrRemove(numArr, ordNumArr, a[++r], 1);
			while (l < quesInfo[i][1])
				addOrRemove(numArr, ordNumArr, a[l++], -1);
			while (r > quesInfo[i][2])
				addOrRemove(numArr, ordNumArr, a[r--], -1);
			while (k < quesInfo[i][3]) {
				k++;
				if (l <= changeInfo[k][0] && changeInfo[k][0] <= r) {
					addOrRemove(numArr, ordNumArr, changeInfo[k][2], -1);
					addOrRemove(numArr, ordNumArr, changeInfo[k][1], 1);
				}
				a[changeInfo[k][0]] = changeInfo[k][1];
			}
			while (k > quesInfo[i][3]) {
				if (l <= changeInfo[k][0] && changeInfo[k][0] <= r) {
					addOrRemove(numArr, ordNumArr, changeInfo[k][1], -1);
					addOrRemove(numArr, ordNumArr, changeInfo[k][2], 1);
				}
				a[changeInfo[k][0]] = changeInfo[k][2];
				k--;
			}
			ans[quesInfo[i][0]] = getAns(numArr);
		}

		for (int i = 1; i <= quesNum; i++)
			System.out.println(ans[i]);

	}
}