There's a famous museum in the city where Kleofáš lives. In the museum, n exhibits (numbered 1 through n) had been displayed for a long time; the i-th of those exhibits has value vi and mass wi.

Then, the museum was bought by a large financial group and started to vary the exhibits. At about the same time, Kleofáš... gained interest in the museum, so to say.

You should process q events of three types:

• type 1 — the museum displays an exhibit with value v and mass w; the exhibit displayed in the i-th event of this type is numbered n + i (see sample explanation for more details)
• type 2 — the museum removes the exhibit with number x and stores it safely in its vault
• type 3 — Kleofáš visits the museum and wonders (for no important reason at all, of course): if there was a robbery and exhibits with total mass at most m were stolen, what would their maximum possible total value be?

For each event of type 3, let s(m) be the maximum possible total value of stolen exhibits with total mass ≤ m.

Formally, let D be the set of numbers of all exhibits that are currently displayed (so initially D = {1, ..., n}). Let P(D) be the set of all subsets of D and let

$$ Then, s(m) is defined as $$s(m) = \max_{S \in G} \left( \sum_{i \in S} v_i \right)$$ Compute s(m) for each $$m \in {1, 2, \ldots, k}$$. Note that the output follows a special format. ## Input The first line of the input contains two space-separated integers n and k (1 ≤ n ≤ 5000, 1 ≤ k ≤ 1000) — the initial number of exhibits in the museum and the maximum interesting mass of stolen exhibits. Then, n lines follow. The i-th of them contains two space-separated positive integers vi and wi (1 ≤ vi ≤ 1 000 000, 1 ≤ wi ≤ 1000) — the value and mass of the i-th exhibit. The next line contains a single integer q (1 ≤ q ≤ 30 000) — the number of events. Each of the next q lines contains the description of one event in the following format: - 1 v w — an event of type 1, a new exhibit with value v and mass w has been added (1 ≤ v ≤ 1 000 000, 1 ≤ w ≤ 1000) - 2 x — an event of type 2, the exhibit with number x has been removed; it's guaranteed that the removed exhibit had been displayed at that time - 3 — an event of type 3, Kleofáš visits the museum and asks his question There will be at most 10 000 events of type 1 and at least one event of type 3. ## Output As the number of values s(m) can get large, output the answers to events of type 3 in a special format. For each event of type 3, consider the values s(m) computed for the question that Kleofáš asked in this event; print one line containing a single number $$\sum_{m=1}^{k} s(m) \cdot p^{m-1} \mod q$$

where p = 107 + 19 and q = 109 + 7.

Print the answers to events of type 3 in the order in which they appear in the input.

见题面 Input 部分

见题面 Output 部分

In the first sample, the numbers of displayed exhibits and values s(1), ..., s(10) for individual events of type 3 are, in order:

$$\text{exhibits } 1,2,3; \quad (s(1),\ldots,s(10))=(5,5,5,30,35,60,65,65,90),$$

$$\text{exhibits } 1,2,3,4,5; \quad (s(1),\ldots,s(10))=(5,5,20,30,42,60,65,65,80,90),$$

$$\text{exhibits } 1,3,5; \quad (s(1),\ldots,s(10))=(5,5,20,30,35,35,50,55,55)$$

$$\text{exhibits } 1,3,5,6; \quad (s(1),\ldots,s(10))=(5,5,20,30,35,40,50,55,60,70).$$

The values of individual exhibits are v1 = 30, v2 = 60, v3 = 5, v4 = 42, v5 = 20, v6 = 40 and their masses are w1 = 4, w2 = 6, w3 = 1, w4 = 5, w5 = 3, w6 = 6.

In the second sample, the only question is asked after removing all exhibits, so s(m) = 0 for any m.