你回到家闻到了一些难闻的气味。它从哪里来?
给你一个数组 a。您必须回答以下问题:
1. 给定两个整数 l 和 r。令 ci 为 i 在 al: r 中出现的次数,其中 al: r 是 a 从第 l 个元素到第 r 个元素的子数组。求 {c0, c1, ..., c109} 的 Mex
2. 给定两个整数 p 到 x。将 ap 更改为 x。
数字多重集的 Mex 是不在该集中的最小非负整数。
请注意,在这个问题中,a 的所有元素都是正数,这意味着 c0 = 0 并且 0 永远不是第二种类型查询的答案。
输入
输入的第一行包含两个整数 n 和 q (1 ≤ n, q ≤ 100 000)——分别是数组的长度和查询的数量。
输入的第二行包含 n 个整数 — a1, a2, ..., an (1 ≤ ai ≤ 109)。
接下来的 q 行每一行都描述一个查询。
第一种类型的查询由三个整数 ti = 1, li, ri 描述,其中 1 ≤ li ≤ ri ≤ n — 子数组的边界。
第二种类型的查询由三个整数 ti = 2, pi, xi 描述,其中 1 ≤ pi ≤ n 是必须更改的元素的索引,1 ≤ xi ≤ 109 是新值。
输出
对于第一种类型的每个查询,输出一个整数 - {c0, c1, ..., c109} 的 Mex。
示例
输入 #1
10 4 1 2 3 1 1 2 2 2 9 9 1 1 1 1 2 8 2 7 1 1 2 8
输出 #1
2 3 2
注意
第一个查询的子数组由单个元素 — 1 组成。
第二个查询的子数组由四个 2、一个 3 和两个 1 组成。
第四个查询的子数组由三个 1、三个 2 和一个 3 组成。