Little T is playing Gold Miner.

To simplify the problem, we assume the miner is located at the origin of the number line. Initially, there are $n$ pieces of gold, each located on the positive half of the number line. The $i$-th piece of gold has coordinate $x_i$ and value $v_i$. It is guaranteed that the sequence $x_i$ is strictly increasing. The time required to obtain the $i$-th piece of gold is $x_i \cdot v_i$. Note: Unlike the original game, the miner can spend $x_i \cdot v_i$ time to obtain a specific piece of gold directly, without needing to clear the gold in front of it.

Little T wants to know the maximum total value of gold that can be obtained within a given time limit. However, there are many levels, and after each level, the gold and the time limit change. Specifically, there are $m$ operations of the following two types:

1. Delete the $y$-th piece of gold. It is guaranteed that this piece has not been deleted before.
2. Query the maximum total value of gold that can be obtained given $k$ units of time. Note: Each piece of gold can be obtained at most once per query, and queries are independent. That is, gold obtained in one query will still be available in subsequent queries.

Can you help Little T achieve the theoretically maximum value for each level?

Input

The first line contains three integers $n, m, k_{\max}$, representing the initial number of gold pieces, the number of operations, and the upper bound of the time limit, respectively.

The next $n$ lines each contain two positive integers $x_i, v_i$, representing the position and value of the $i$-th piece of gold.

The next $m$ lines each contain two positive integers, in the format 1 y or 2 k, representing an operation.

Output

For each query operation, output one integer per line representing the answer.

Examples

Input 1

3 8 50
3 3
4 2
6 4
2 25
2 8
2 7
2 12
1 2
2 25
1 3
2 40

Output 1

5
2
0
3
4
3

Note

For the 1st query, the optimal strategy is to obtain the 1st and 2nd pieces of gold. The total time is $3 \cdot 3 + 4 \cdot 2 = 17 \leq 25$, and the total value is $3 + 2 = 5$.

For the 2nd query, the optimal strategy is to obtain the 2nd piece of gold. The total time is $8$, and the total value is $2$.

For the 3rd query, the optimal strategy is to do nothing. The total time is $0$, and the total value is $0$.

For the 4th query, the optimal strategy is to obtain the 1st piece of gold. The total time is $9$, and the total value is $3$.

For the 5th query, since the 2nd piece of gold has been deleted, the optimal strategy is to obtain the 3rd piece of gold. The total time is $24$, and the total value is $4$.

For the 6th query, since both the 2nd and 3rd pieces of gold have been deleted, the optimal strategy is to obtain the 1st piece of gold. The total time is $9$, and the total value is $3$.

Constraints

For all data, $1 \leq n \leq k_{\max} \leq 2 \times 10^6$, $1 \leq x_i \cdot v_i \leq k_{\max}$, $1 \leq x_1 < x_2 < \cdots < x_n \leq k_{\max}$, $1 \leq m \leq 5000$, $1 \leq k \leq k_{\max}$.

Subtask 1 (11 points): $n, k_{\max} \leq 5000$.

Subtask 2 (13 points): $m = 1$.

Subtask 3 (15 points): $n \leq 5000$.

Subtask 4 (21 points): $n, k_{\max} \leq 3 \times 10^5$.

Subtask 5 (40 points): No special restrictions.

Note

The input size for this problem is large; please use fast I/O methods.