题目描述

小 T 在玩黄金矿工。

为了简化问题，我们假设矿工位于数轴原点，初始时有 $n$ 块金子，且每块金子都位于数轴的正半轴上。第 $i$ 块金子的坐标为 $x_i$，价值为 $v_i$。保证序列 $x_i$ 严格递增。

获得第 $i$ 块金子所需的时间为 $x_i\cdot v_i$。注意：与原版游戏不同，矿工可以花 $x_i\cdot v_i$ 的时间直接获得某块金子，而不需要把它前面的金子先清理掉。

小 T 想知道在时限内能获得的金子价值之和最大是多少。但关卡有很多，每次通关后，金子以及时限会发生一些变化。具体来说，共有 $m$ 次操作，操作有以下两种：

1. 删除第 $y$ 块金子，保证该金子之前没被删除过；
2. 询问在有 $k$ 个单位时间时，获得的金子价值之和最大是多少。每块金子每次询问只能获得一次，且询问之间相互独立。也就是说，这次获得的金子在之后的询问中依然会出现。

请你帮助小 T 求出每次询问的最优答案。

输入格式

第一行三个整数 $n,m,k_{\max}$，分别表示初始金子数、操作数和时限上界。

接下来 $n$ 行，每行两个正整数 $x_i,v_i$，表示第 $i$ 块金子的位置和价值。

接下来 $m$ 行，每行两个正整数，形如 1 y 或 2 k，表示一次操作。

输出格式

对于每个询问操作，输出一行一个整数表示答案。

样例

输入

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

输出

5
2
0
3
4
3

样例解释

对于第 1 个询问，最佳方案是获得第 1 块和第 2 块金子，总用时为 $3\cdot3+4\cdot2=17\le25$，总价值为 $3+2=5$。

对于第 2 个询问，最佳方案是获得第 2 块金子，总价值为 $2$。

对于第 3 个询问，最佳方案是什么也不做，总价值为 $0$。

对于第 4 个询问，最佳方案是获得第 1 块金子，总价值为 $3$。

对于第 5 个询问，由于第 2 块金子已被删除，最佳方案是获得第 3 块金子，总价值为 $4$。

对于第 6 个询问，由于第 2 块和第 3 块金子均已被删除，最佳方案是获得第 1 块金子，总价值为 $3$。

数据范围

对于所有数据：

• $1\le n\le k_{\max}\le 2\times10^6$；
• $1\le x_i\cdot v_i\le k_{\max}$；
• $1\le x_1<x_2<\cdots<x_n\le k_{\max}$；
• $1\le m\le 5000$；
• 询问中 $1\le k\le k_{\max}$；
• 删除操作保证对应金子此前没有被删除。

子任务：

提示

本题输入量较大，请使用较快的输入方式。