定义一个函数 $f(a)$，其参数为一个包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ 的序列（每个整数在 $[0, n]$ 范围内），并返回一个序列 $b_1, b_2, \dots, b_n$，其中 $b_i$ 是数字 $i$ 在序列 $a_1, a_2, \dots, a_n$ 中出现的次数。

此外，定义其 $k$ 重复合函数为： $$f^k(a) = \begin{cases} a & \text{for } k = 0, \\ f(f^{k-1}(a)) & \text{for } k > 0. \end{cases}$$

给定一个序列 $a_1, a_2, \dots, a_n$，你需要处理两种类型的查询： $1 \ v \ x$ —— 将 $a_v$ 的值修改为 $x$。 $2 \ k \ v$ —— 输出序列 $f^k(a)$ 的第 $v$ 个元素。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n \le 300\,000; 1 \le q \le 500\,000$)，分别表示输入序列的长度和查询次数。 第二行包含一个包含 $n$ 个整数的序列 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le n$)。 接下来的 $q$ 行包含查询描述，格式如题目所述。满足 $1 \le v \le n$，$0 \le x \le n$ 以及 $0 \le k \le 300\,000$。 保证至少存在一个第二类型的查询。

输出格式

输出应包含与第二类型查询数量相同的行数。第 $i$ 行应包含一个整数，即第 $i$ 个第二类型查询的答案。

样例

输入 1

6 6
2 1 2 3 0 3
2 3 2
1 5 2
2 0 2
1 2 3
2 0 2
2 2 3

输出 1

1
1
3
2

说明

让我们分析最后一个查询。我们有： $f^0(a) = [2, 3, 2, 3, 2, 3]$ $f^1(a) = [0, 3, 3, 0, 0, 0]$ * $f^2(a) = [0, 0, 2, 0, 0, 0]$

该查询的答案为 $2$。