P15681 分糖果

现有一个长度为 $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 解释 - 进行第一个操作时，$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$。 ::cute-table{tuack} | 测试点编号 | $n,q\le$ | 特殊性质 | | :--------: | :-----------: | :------: | | $1$ | $5$ | A | | $2$ | $5$ | B | | $3$ | $400$ | BC | | $4\sim5$ | $400$ | 无 | | $6$ | $5000$ | BC | | $7$ | $5000$ | B | | $8$ | $5000$ | C | | $9$ | $5000$ | 无 | | $10$ | $10^5$ | BC | | $11$ | $10^5$ | B | | $12$ | $10^5$ | C | | $13\sim14$ | $10^5$ | 无 | | $15$ | $5\times10^5$ | A | | $16$ | $5\times10^5$ | BC | | $17$ | $5\times10^5$ | B | | $18$ | $5\times10^5$ | C | | $19\sim20$ | $5\times10^5$ | 无 | - 特殊性质 A：保证 $m \le 7$。 - 特殊性质 B：保证 $m=10^{12}$。 - 特殊性质 C：保证没有第一种操作。