题目描述

现有一个长度为 $n$ 的数列 $a_1,a_2,\dots,a_n$ 和 $q$ 个操作，操作共两种：

1. 给定 $x,y$，你需要将 $a_x$ 的值修改为 $y$；
2. 给定 $m,k$，你需要求出：若现在一共有 $m$ 个篮子和 $n$ 个人，第 $i$ 个人会选择不同的 $a_i$ 个篮子并往这 $a_i$ 个篮子中各放 $1$ 颗糖，恰好装有 $k$ 颗糖的篮子的数量的最大值。

输入格式

第一行包含三个整数 $c,n,q$，其中 $c$ 表示测试点编号。样例满足 $c=0$。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$。

接下来 $q$ 行，第 $i$ 行包含三个整数，格式形如 $1\ x\ y$ 或 $2\ m\ k$，分别表示第一种操作和第二种操作。

输出格式

对于每个第二种操作，输出一行，包含一个整数表示答案。

样例 1 输入

0 3 4
1 2 5
2 5 2
1 3 3
2 4 1
2 5 0

样例 1 输出

3
3
2

样例 1 解释

• 进行第一个操作时，$a=\{1,2,5\}$，$m=5$，$k=2$；第 $1$ 个人可以选择往第 $1$ 个篮子中放 $1$ 颗糖，第 $2$ 个人可以选择往第 $2$ 个篮子和第 $3$ 个篮子中放 $1$ 颗糖，第 $3$ 个人只能选择往所有篮子中均放 $1$ 颗糖，此时第 $1,2,3$ 个篮子中均有恰好 $2$ 颗糖，容易证明这样可以使装有恰好 $2$ 颗糖的篮子的数量最大化。
• 进行第三个操作时，$a=\{1,2,3\}$，$m=4$，$k=1$；第 $1$ 个人可以选择往第 $1$ 个篮子中放 $1$ 颗糖，第 $2$ 个人可以选择往第 $1$ 个篮子和第 $2$ 个篮子中放 $1$ 颗糖，第 $3$ 个人可以选择往第 $1,3,4$ 个篮子中均放 $1$ 颗糖，此时第 $2,3,4$ 个篮子中均有恰好 $1$ 颗糖，容易证明这样可以使装有恰好 $1$ 颗糖的篮子的数量最大化。
• 进行第四个操作时，$a=\{1,2,3\}$，$m=5$，$k=0$；第 $1$ 个人可以选择往第 $1$ 个篮子中放 $1$ 颗糖，第 $2$ 个人可以选择往第 $1$ 个篮子和第 $2$ 个篮子中放 $1$ 颗糖，第 $3$ 个人可以选择往第 $1,2,3$ 个篮子中均放 $1$ 颗糖，此时第 $4$ 个篮子和第 $5$ 个篮子中均有恰好 $1$ 颗糖，容易证明这样可以使装有恰好 $0$ 颗糖的篮子的数量最大化。

样例 2

见 candy/candy2.in 与 candy/candy2.ans。

该组样例满足测试点 $4$ 的限制。

样例 3

见 candy/candy3.in 与 candy/candy3.ans。

该组样例满足测试点 $9$ 的限制。

样例 4

见 candy/candy4.in 与 candy/candy4.ans。

该组样例满足测试点 $10$ 的限制。

样例 5

见 candy/candy5.in 与 candy/candy5.ans。

该组样例满足测试点 $15$ 的限制。

样例 6

见 candy/candy6.in 与 candy/candy6.ans。

该组样例满足测试点 $17$ 的限制。

样例 7

见 candy/candy7.in 与 candy/candy7.ans。

该组样例满足测试点 $18$ 的限制。

样例 8

见 candy/candy8.in 与 candy/candy8.ans。

该组样例满足测试点 $20$ 的限制。

数据范围

对于所有测试数据，保证：

• $1 \le n,q \le 5\times10^5$；
• $1 \le a_i \le 10^6$；
• $1 \le x \le n$，$1 \le y \le 10^6$；
• $\max a_i \le m \le 10^{12}$，$0 \le k \le n$。

• 特殊性质 A：保证 $m \le 7$。
• 特殊性质 B：保证 $m=10^{12}$。
• 特殊性质 C：保证没有第一种操作。