A Museum Robbery

题意翻译

有n个展品正在被展览，每一个展品都有一价值v个和一个混乱度w，现在有m次操作： 1 v w :加入一个新的展品,价值为v,混乱度为w 2 x :删除第x个展品（一开始的展品也参与编号，且保证此展品此时存在） 3 ：进行询问 记，其中，$D$ 是当前展品的集合，$P(D)$ 是 $D$ 的幂集（即 D 的全部子集）。 对于每一个询问，只需输出$\sum_{m=1}^{k}{s(m)*p^{m-1}\ mod\ q}$其中，$p=10^{7}+19,q=10^{9}+7$ 操作1最多10000次。

题目描述

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.

输入输出样例

输入样例 #1

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

输出样例 #1

556674384
168191145
947033915
181541912

输入样例 #2

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

输出样例 #2

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