CF311C.Fetch the Treasure

Rainbow built h cells in a row that are numbered from 1 to h from left to right. There are n cells with treasure. We call each of these n cells "Treasure Cell". The i-th "Treasure Cell" is the a__i-th cell and the value of treasure in it is c__i dollars.

Then, Freda went in the first cell. For now, she can go just k cells forward, or return to the first cell. That means Freda was able to reach the 1st, (k + 1)-th, (2·k + 1)-th, (3·k + 1)-th cells and so on.

Then Rainbow gave Freda m operations. Each operation is one of the following three types:

1. Add another method x: she can also go just x cells forward at any moment. For example, initially she has only one method k. If at some moment she has methods _a_1, _a_2, ..., a__r then she can reach all the cells with number in form , where v__i — some non-negative integer.
2. Reduce the value of the treasure in the x-th "Treasure Cell" by y dollars. In other words, to apply assignment c__x = c__x - y.
3. Ask the value of the most valuable treasure among the cells Freda can reach. If Freda cannot reach any cell with the treasure then consider the value of the most valuable treasure equal to 0, and do nothing. Otherwise take the most valuable treasure away. If several "Treasure Cells" have the most valuable treasure, take the "Treasure Cell" with the minimum number (not necessarily with the minimum number of cell). After that the total number of cells with a treasure is decreased by one.

As a programmer, you are asked by Freda to write a program to answer each query.

Rainbow 从左到右依次建造了 $ h $ 个格子，编号为 $ 1 $ 到 $ h $。其中有 $ n $ 个格子藏有宝藏，我们将这 $ n $ 个格子统称为“宝藏格子”。第 $ i $ 个“宝藏格子”位于第 $ a_i $ 个格子中，其中宝藏价值为 $ c_i $ 美元。

随后，Freda 进入第 $ 1 $ 个格子。此时她每次只能向前移动恰好 $ k $ 个格子，或返回第 $ 1 $ 个格子。这意味着 Freda 当前能够到达的格子编号为：$ 1 $、$ k+1 $、$ 2k+1 $、$ 3k+1 $，依此类推。

接着，Rainbow 给 Freda 下达了 $ m $ 个操作指令。每个操作属于以下三种类型之一：

1. 添加一种新移动方式 $ x $：此后她还可以在任意时刻向前恰好移动 $ x $ 个格子。例如，初始时她仅有移动方式 $ k $；若在某一时刻她拥有的移动方式集合为 $ a_1, a_2, \dots, a_r $，则她能到达的所有格子编号形如
   ，
   其中每个 $ v_i $ 均为非负整数。

2. 降低第 $ x $ 个“宝藏格子”的宝藏价值：将其宝藏价值减少 $ y $ 美元。即执行赋值操作 $ c_x = c_x - y $。

3. 查询 Freda 能到达的所有格子中，宝藏价值最高的那个宝藏的价值：若 Freda 无法到达任何藏有宝藏的格子，则认为最高价值为 $ 0 $，且不进行任何操作；否则，取走该最高价值的宝藏。若存在多个“宝藏格子”具有相同的最高价值，则取其中编号最小的那个（注意：此处“编号最小”指“宝藏格子”的序号 $ x $ 最小，而非其所处格子位置编号最小）。执行此操作后，“宝藏格子”的总数减 $ 1 $。

作为程序员，你需要为 Freda 编写一个程序，以回答每一次查询。

The first line of the input contains four integers: h (1 ≤ h ≤ 1018), n, m (1 ≤ n, m ≤ 105) and k (1 ≤ k ≤ 104).

Each of the next n lines contains two integers: a__i (1 ≤ a__i ≤ h), c__i (1 ≤ c__i ≤ 109). That means the i-th "Treasure Cell" is the a__i-th cell and cost of the treasure in that cell is c__i dollars. All the a__i are distinct.

Each of the next m lines is in one of the three following formats:

• "1 x" — an operation of type 1, 1 ≤ x ≤ h;
• "2 x y" — an operation of type 2, 1 ≤ x ≤ n, 0 ≤ y < c__x;
• "3" — an operation of type 3.

There are at most 20 operations of type 1. It's guaranteed that at any moment treasure in each cell has positive value. It's guaranteed that all operations is correct (no operation can decrease the value of the taken tresure).

Please, do not use the %lld specifier to read 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

输入的第一行包含四个整数：$h$（$1 \le h \le 10^{18}$）、$n$、$m$（$1 \le n, m \le 10^5$）和 $k$（$1 \le k \le 10^4$）。

接下来的 $n$ 行，每行包含两个整数：$a_i$（$1 \le a_i \le h$）、$c_i$（$1 \le c_i \le 10^9$）。这表示第 $i$ 个“宝藏格子”位于第 $a_i$ 个格子，其中宝藏的价值为 $c_i$ 美元。所有 $a_i$ 互不相同。

再接下来的 $m$ 行，每行属于以下三种格式之一：

• 1 x —— 类型 1 的操作，其中 $1 \le x \le h$；
• 2 x y —— 类型 2 的操作，其中 $1 \le x \le n$，$0 \le y < c_x$；
• 3 —— 类型 3 的操作。

类型 1 的操作至多出现 20 次。保证在任意时刻每个格子中的宝藏价值均为正数。保证所有操作均合法（即不存在任何操作会降低已被获取的宝藏的价值）。

请注意：在 C++ 中读取 64 位整数时，请勿使用 %lld 说明符。推荐使用 cin / cout 流，或 %I64d 说明符。

For each operation of type 3, output an integer indicates the value (in dollars) of the most valuable treasure among the "Treasure Cells" Freda can reach. If there is no such treasure, output 0.

对于每个类型为 3 的操作，输出一个整数，表示 Freda 能够到达的所有“宝藏格子”中价值最高者的价值（单位：美元）。若不存在这样的宝藏，则输出 0。

In the sample, there are 10 cells and 3 "Treasure Cells". The first "Treasure Cell" is cell 5, having 50 dollars tresure in it. The second "Treasure Cell" is cell 7, having 60 dollars tresure in it. The third "Treasure Cell" is cell 8, having 100 dollars tresure in it.

At first, Freda can only reach cell 1, 3, 5, 7 and 9. In the first operation, we reduce the value in the second "Treasure Cell" from 60 to 55. Then the most valuable treasure among the "Treasure Cells" she can reach is max(50, 55) = 55. After the third operation, she can also go 3 cells forward each step, being able to reach cell 1, 3, 4, 5, 6, 7, 8, 9, 10. So the most valuable tresure is 100.

Noticed that she took the 55 dollars and 100 dollars treasure away, so the last answer is 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。