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*<sub class="lower-index">*i*</sub>-th cell and the value of treasure in it is *c*<sub class="lower-index">*i*</sub> 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*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*r*</sub> then she can reach all the cells with number in form <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/14aebaba37756f1fdc32ea2da9a70f94b18b7523.png" style="max-width: 100.0%;max-height: 100.0%;"/>, where *v*<sub class="lower-index">*i*</sub> — some non-negative integer. 1.  Reduce the value of the treasure in the *x*-th "Treasure Cell" by *y* dollars. In other words, to apply assignment *c*<sub class="lower-index">*x*</sub> = *c*<sub class="lower-index">*x*</sub> - *y*. 1.  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.
The first line of the input contains four integers: *h* (1 ≤ *h* ≤ 10<sup class="upper-index">18</sup>), *n*, *m* (1 ≤ *n*, *m* ≤ 10<sup class="upper-index">5</sup>) and *k* (1 ≤ *k* ≤ 10<sup class="upper-index">4</sup>).

Each of the next *n* lines contains two integers: *a*<sub class="lower-index">*i*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ *h*), *c*<sub class="lower-index">*i*</sub> (1 ≤ *c*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>). That means the *i*-th "Treasure Cell" is the *a*<sub class="lower-index">*i*</sub>-th cell and cost of the treasure in that cell is *c*<sub class="lower-index">*i*</sub> dollars. All the *a*<sub class="lower-index">*i*</sub> 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* &lt; *c*<sub class="lower-index">*x*</sub>; -  "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.
print("_RANDOM_GUESS_1689438647.055181")# 1689438647.0551987