A Museum Robbery

初始有 $n$ 件展品（标号 $1$ 到 $n$），其中第 $i$ 件展品有大小为 $v_i$ 的**价值**，$w_i$ 的**质量**。 接下来会发生 $q$ 个事件，每个事件为以下三种类型之一： - 添加一个价值为 $v$，质量为 $w$ 的展品。记上一次该操作添加展品的编号为 $t$（如果这是第一次，则默认为 $t = n$），则本次添加的展品的编号为 $t+1$； - 删除编号为 $x$ 的展品； - 进行一次询问，其中询问方式如下。 对于最开始给定的正整数 $k$，请你输出： $$ \sum \limits_{m = 1}^k s(m) \times p^{m-1} \bmod q $$ （其中 $p = 10^7 + 19, q = 10^9 + 7$） $s(m)$ 的定义如下： 设当前展品编号集合为 $D$，$S$ 是 $D$ 的一个子集，且满足 $\sum \limits_{i \in S} w_i \leq m$，则 $s(m)$ 是 $\sum \limits_{i \in S} v_i$ 的最大值。 **输入格式** 第一行，两个正整数 $n, k$。 接下来 $n$ 行中，第 $i$ 行包含两个正整数 $v_i, w_i$，表示第 $i$ 个展品的价值和质量。 接下来一行，一个正整数 $q$。 接下来 $q$ 行中，每一行可能为如下事件之一： - `1 v w`，表示事件 $1$，即添加一个价值为 $v$，质量为 $w$ 的展品。编号如题意； - `2 x`，表示事件 $2$，即删除展品 $x$。保证该展品此前未被删除； - `3`，表示事件 $3$，一次询问。 保证最多有 $10000$ 次事件 $1$，至少有一次事件 $3$。 **输出格式** 对于每一次事件 $3$，输出一行一个正整数，表示答案。输出的内容如题意。 **数据范围** $1 \leq n \leq 5 \times 10^3$，$1 \leq q \leq 3 \times 10^4$，$1 \leq k, w_i, w \leq 10^3$，$1 \leq v_i, v \leq 10^6$。

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.

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}<=1000000 $ , $ 1<=w_{i}<=1000 $ ) — the value and mass of the $ i $ -th exhibit. The next line contains a single integer $ q $ ( $ 1<=q<=30000 $ ) — 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<=1000000 $ , $ 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 $ 10000 $ events of type 1 and at least one event of type 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=10^{7}+19 $ and $ q=10^{9}+7 $ . Print the answers to events of type 3 in the order in which they appear in the input.

3 10
30 4
60 6
5 1
9
3
1 42 5
1 20 3
3
2 2
2 4
3
1 40 6
3

556674384
168191145
947033915
181541912

3 1000
100 42
100 47
400 15
4
2 2
2 1
2 3
3

0

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 $ .