Rainbow 在一行中构建了 h 个单元格,从左到右编号为 1 到 h。有 n 个有宝藏的单元格。我们将这 n 个细胞中的每一个称为“宝藏细胞”。第 i 个“宝藏单元”是第 ai 个单元,其中的宝藏价值为 ci 美元。
然后,Freda 走进了第一个牢房。目前,她只能向前移动 k 个单元格,或者返回到第一个单元格。这意味着 Freda 能够到达第 1 个、第 (k + 1) 个、第 (2·k + 1) 个、第 (3·k + 1) 个单元格,依此类推。
然后 Rainbow 给了 Freda m 操作。每个操作都是以下三种类型之一:
1.添加另一个方法x:她也可以随时向前移动x个单元格。例如,最初她只有一种方法 k。如果在某个时刻她有方法 a1, a2, ..., ar 那么她可以到达所有具有 $$1 + \sum_{i=1}^{r} v_i \cdot a_i$$ 形式的数字的单元格,其中 vi — 某个非负整数。
2. 将第 x 个“宝藏单元”中的宝藏价值减少 y 美元。换句话说,应用赋值 cx = cx - y。
3.询问Freda可以到达的单元格中最有价值的宝藏的价值。如果 Freda 无法到达任何带有宝藏的单元格,则将最有价值的宝藏的价值视为 0,并且不执行任何操作。否则,夺走最珍贵的宝藏。如果有几个“宝藏细胞”拥有最有价值的宝藏,则取数量最少的“宝藏细胞”(不一定是细胞数量最少的)。之后,拥有宝藏的细胞总数就会减少一个。
作为一名程序员,Freda 要求您编写一个程序来回答每个查询。
输入
输入的第一行包含四个整数:h(1 ≤ h ≤ 1018)、n、m(1 ≤ n、m ≤ 105)和 k(1 ≤ k ≤ 104)。
接下来的 n 行每行包含两个整数:ai (1 ≤ ai ≤ h)、ci (1 ≤ ci ≤ 109)。这意味着第 i 个“宝藏单元”是第 ai 个单元,该单元中的宝藏成本为 ci 美元。所有的ai都是不同的。
接下来的 m 行中的每一行均采用以下三种格式之一:
- "1 x" — 类型 1 的操作,1 ≤ x ≤ h;
- "2 x y" — 类型 2 的运算,1 ≤ x ≤ n, 0 ≤ y < cx;
- "3" — 类型 3 的操作。
类型1的操作最多有20个。保证在任何时刻每个单元格中的宝藏都有正值。保证所有操作正确(任何操作都不会减少所获取宝藏的价值)。
请不要使用 %lld 说明符读取 С++ 中的 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。
输出
对于类型 3 的每个操作,输出一个整数,表示 Freda 可以达到的“宝藏单元”中最有价值的宝藏的价值(以美元为单位)。如果没有这样的宝物,则输出0。
示例
输入 #1
10 3 5 2 5 50 7 60 8 100 2 2 5 3 1 3 3 3
输出 #1
55 100 50
注意
样本中,有10个细胞和3个“宝藏细胞”。第一个“宝藏格”是 5 号格,里面有 50 美元的宝藏。第二个“宝藏格”是7号格,里面有60美元的宝藏。第三个“宝藏格”是8号格,里面有100美元的宝藏。
起初,Freda只能到达1、3、5、7和9号格。在第一次操作中,我们将第二个“宝藏格”中的值从60减少到55。那么她能到达的“宝藏格”中最有价值的宝藏是max(50, 55) = 55。第三次操作后,她还可以每一步前进3个格,能够到达格子1、3、4、5、6、7、8、9、10。所以最有价值的宝藏是100。
注意到她拿走了55块钱和100块钱的宝物,所以最后的答案是50。