Problem Description

You are given a sequence $a_1,a_2,\dots,a_n$ of length $n$ and $q$ operations. There are two types of operations in total:

1. Given $x,y$, you need to modify the value of $a_x$ to $y$.
2. Given $m,k$, you need to compute the following: suppose there are currently $m$ baskets and $n$ people. The $i$-th person will choose $a_i$ distinct baskets and put $1$ candy into each of these $a_i$ baskets. Find the maximum possible number of baskets that end up with exactly $k$ candies.

Input Format

The first line contains three integers $c,n,q$, where $c$ denotes the test point ID. The samples satisfy $c=0$.

The second line contains $n$ integers $a_1,a_2,\dots,a_n$.

The next $q$ lines each contain three integers, in the form $1\ x\ y$ or $2\ m\ k$, representing the first type of operation and the second type of operation, respectively.

Output Format

For each operation of the second type, output one line containing one integer, which is the answer.

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

3
3
2

Hint

Explanation for Sample 1

• For the first operation, $a=\{1,2,5\}$, $m=5$, $k=2$. Person $1$ can choose to put $1$ candy into basket $1$. Person $2$ can choose to put $1$ candy into basket $2$ and basket $3$. Person $3$ can only choose to put $1$ candy into all baskets. Then baskets $1,2,3$ each have exactly $2$ candies. It is easy to prove that this maximizes the number of baskets with exactly $2$ candies.
• For the third operation, $a=\{1,2,3\}$, $m=4$, $k=1$. Person $1$ can choose to put $1$ candy into basket $1$. Person $2$ can choose to put $1$ candy into basket $1$ and basket $2$. Person $3$ can choose to put $1$ candy into baskets $1,3,4$. Then baskets $2,3,4$ each have exactly $1$ candy. It is easy to prove that this maximizes the number of baskets with exactly $1$ candy.
• For the fourth operation, $a=\{1,2,3\}$, $m=5$, $k=0$. Person $1$ can choose to put $1$ candy into basket $1$. Person $2$ can choose to put $1$ candy into basket $1$ and basket $2$. Person $3$ can choose to put $1$ candy into baskets $1,2,3$. Then basket $4$ and basket $5$ each have exactly $1$ candy. It is easy to prove that this maximizes the number of baskets with exactly $0$ candies.

Sample 2

See candy/candy2.in and candy/candy2.ans.

This sample set satisfies the constraints of test point $4$.

Sample 3

See candy/candy3.in and candy/candy3.ans.

This sample set satisfies the constraints of test point $9$.

Sample 4

See candy/candy4.in and candy/candy4.ans.

This sample set satisfies the constraints of test point $10$.

Sample 5

See candy/candy5.in and candy/candy5.ans.

This sample set satisfies the constraints of test point $15$.

Sample 6

See candy/candy6.in and candy/candy6.ans.

This sample set satisfies the constraints of test point $17$.

Sample 7

See candy/candy7.in and candy/candy7.ans.

This sample set satisfies the constraints of test point $18$.

Sample 8

See candy/candy8.in and candy/candy8.ans.

This sample set satisfies the constraints of test point $20$.

Constraints

For all testdata, it is guaranteed that:

• $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}

• Special property A: it is guaranteed that $m \le 7$.
• Special property B: it is guaranteed that $m=10^{12}$.
• Special property C: it is guaranteed that there is no operation of the first type.

Translated by ChatGPT 5