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

1. Given $x, y$, you need to update the value of $a_x$ to $y$.
2. Given $m, k$, you need to find the maximum number of baskets that contain exactly $k$ candies, assuming there are $m$ baskets and $n$ people, where the $i$-th person chooses $a_i$ distinct baskets and places $1$ candy into each of these $a_i$ baskets.

Input

The first line contains three integers $c, n, q$, where $c$ is the test case number. The sample satisfies $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 format $1\ x\ y$ or $2\ m\ k$, representing the first and second types of operations, respectively.

Output

For each operation of the second type, output a single integer representing the answer on a new line.

Examples

Input 1

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

Output 1

3
3
2

Note 1

• For the first operation: $a=\{1,2,5\}$, $m=5$, $k=2$. The first person can choose to put $1$ candy in the first basket, the second person can choose to put $1$ candy in the second and third baskets, and the third person must choose to put $1$ candy in all baskets. At this point, the first, second, and third baskets each contain exactly $2$ candies. It is easy to prove that this maximizes the number of baskets containing exactly $2$ candies.
• For the third operation: $a=\{1,2,3\}$, $m=4$, $k=1$. The first person can choose to put $1$ candy in the first basket, the second person can choose to put $1$ candy in the first and second baskets, and the third person can choose to put $1$ candy in the first, third, and fourth baskets. At this point, the second, third, and fourth baskets each contain exactly $1$ candy. It is easy to prove that this maximizes the number of baskets containing exactly $1$ candy.
• For the fourth operation: $a=\{1,2,3\}$, $m=5$, $k=0$. The first person can choose to put $1$ candy in the first basket, the second person can choose to put $1$ candy in the first and second baskets, and the third person can choose to put $1$ candy in the first, second, and third baskets. At this point, the fourth and fifth baskets each contain exactly $0$ candies. It is easy to prove that this maximizes the number of baskets containing exactly $0$ candies.

Examples 2-8

See candy/candy2.in through candy/candy8.in and their corresponding .ans files. These samples satisfy the constraints for test cases 4, 9, 10, 15, 17, 18, and 20, respectively.

Constraints

For all test cases, 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$

• Special Property A: Guaranteed $m \le 7$.
• Special Property B: Guaranteed $m=10^{12}$.
• Special Property C: Guaranteed no operations of the first type.