CF601E.A Museum Robbery

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 v__i and mass w__i.

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

Compute s(m) for each . Note that the output follows a special format.

克莱奥法什（Kleofáš）所在的城市有一座著名的博物馆。馆内长期展出 $ n $ 件展品（编号为 $ 1 $ 至 $ n $）；其中第 $ i $ 件展品的价值为 $ v_i $，质量为 $ w_i $。

随后，该博物馆被一家大型金融集团收购，并开始频繁更换展品。几乎在同一时期，克莱奥法什……也对这座博物馆产生了兴趣（姑且这么说吧）。

你需要处理 $ q $ 个事件，事件共分三种类型：

• 类型 1 — 博物馆新增一件价值为 $ v $、质量为 $ w $ 的展品；该类型中第 $ i $ 次发生的事件所新增的展品编号为 $ n + i $（更多细节请参见样例说明）；
• 类型 2 — 博物馆移除编号为 $ x $ 的展品，并将其安全存入金库；
• 类型 3 — 克莱奥法什参观博物馆，并好奇地思考（当然，完全出于无关紧要的原因）：倘若发生抢劫，被盗展品的总质量至多为 $ m $，那么它们可能达到的最大总价值是多少？

对于每个类型 3 的事件，令 $ s(m) $ 表示总质量不超过 $ m $ 的被盗展品所能取得的最大总价值。

形式化地，令 $ D $ 表示当前正在展出的所有展品的编号集合（初始时 $ D = {1, \dots, n} $）。令 $ P(D) $ 表示 $ D $ 的所有子集构成的集合，并定义

则 $ s(m) $ 定义为

对每个 ，计算 $ s(m) $。注意：输出遵循一种特殊格式。

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 v__i and w__i (1 ≤ v__i ≤ 1 000 000, 1 ≤ w__i ≤ 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.

输入的第一行包含两个以空格分隔的整数 $n$ 和 $k$（$1 \leq n \leq 5000$，$1 \leq k \leq 1000$）——分别表示博物馆中初始展品的数量以及被盗展品的最大有趣质量。

接下来是 $n$ 行。其中第 $i$ 行包含两个以空格分隔的正整数 $v_i$ 和 $w_i$（$1 \leq v_i \leq 1\,000\,000$，$1 \leq w_i \leq 1000$）——分别表示第 $i$ 件展品的价值和质量。

随后一行包含一个整数 $q$（$1 \leq q \leq 30\,000$）——表示事件总数。

接下来的 $q$ 行每行描述一个事件，格式如下：

• 1 v w —— 类型 1 的事件：一件新展品被加入，其价值为 $v$、质量为 $w$（$1 \leq v \leq 1\,000\,000$，$1 \leq w \leq 1000$）；
• 2 x —— 类型 2 的事件：编号为 $x$ 的展品被移除；保证被移除的展品当时确实在馆内展出；
• 3 —— 类型 3 的事件：Kleofáš 参观博物馆并提出他的问题。

类型 1 的事件至多有 $10\,000$ 次，且至少存在一次类型 3 的事件。

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

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.

由于 s(m) 的值可能非常大，因此需以特殊格式输出类型 3 事件的答案。

对于每个类型 3 的事件，考虑 Kleofáš 在该事件中所提出问题所计算出的 s(m) 值；输出一行，其中仅包含一个数字

其中 p = 10⁷ + 19，q = 10⁹ + 7。

按输入中类型 3 事件出现的顺序依次输出其答案。

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

The values of individual exhibits are _v_1 = 30, _v_2 = 60, _v_3 = 5, _v_4 = 42, _v_5 = 20, _v_6 = 40 and their masses are _w_1 = 4, _w_2 = 6, _w_3 = 1, _w_4 = 5, _w_5 = 3, _w_6 = 6.

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

在第一个样例中，各次类型 3 事件所展示的展品数量及对应的值 $s(1),\ \dots,\ s(10)$ 依次为：

各展品的值分别为 $v_1 = 30,\ v_2 = 60,\ v_3 = 5,\ v_4 = 42,\ v_5 = 20,\ v_6 = 40$，其质量分别为 $w_1 = 4,\ w_2 = 6,\ w_3 = 1,\ w_4 = 5,\ w_5 = 3,\ w_6 = 6$。

在第二个样例中，唯一一次询问发生在所有展品均被移除之后，因此对任意 $m$ 均有 $s(m) = 0$。