Kleofáš 居住的城市有一个著名的博物馆。博物馆内有n件展品(编号为1到n)已长期陈列;这些展品中的第 i 个具有值 vi 和质量 wi。
随后,博物馆被一家大型财团收购,并开始改变展品。大约在同一时间,Kleofáš...可以说对博物馆产生了兴趣。
您应该处理三种类型的事件:
- 类型 1 — 博物馆展示价值为 v、质量为 w 的展品;第 i 个此类活动中展示的展品编号为 n + i(更多详细信息请参阅示例说明)
- 类型 2 — 博物馆移除编号为 x 的展品并将其安全地存放在金库中
- 类型 3 - Kleofáš 参观了博物馆并想知道(当然,根本没有什么重要原因):如果发生抢劫并且总质量最多为 m 的展品被盗,它们的最大可能总价值是多少?
对于类型 3 的每个事件,令 s(m) 为总质量 ≤ m 的被盗展品的最大可能总值。
正式地,令 D 为当前展示的所有展品的编号集合(因此最初 D = {1, ..., n})。设 P(D) 为 D 的所有子集的集合,并令
$$$$
那么,s(m) 定义为
$$s(m) = \max_{S \in G} \left( \sum_{i \in S} v_i \right)$$
计算 \{1, 2, \ldots, k\}$$ 中每个 $$m 的 s(m)。请注意,输出遵循特殊格式。
输入
输入的第一行包含两个空格分隔的整数 n 和 k (1 ≤ n ≤ 5000, 1 ≤ k ≤ 1000) - 博物馆中展品的初始数量和被盗展品的最大有趣质量。
然后,接下来是 n 行。其中第 i 个包含两个空格分隔的正整数 vi 和 wi (1 ≤ vi ≤ 1 000 000, 1 ≤ wi ≤ 1000)——第 i 个展品的价值和质量。
下一行包含一个整数 q (1 ≤ q ≤ 30 000) — 事件数。
接下来的 q 行每一行都包含一个事件的描述,格式如下:
- 1 v w — 类型 1 的事件,添加了值为 v 和质量 w 的新展品 (1 ≤ v ≤ 1 000 000, 1 ≤ w ≤ 1000)
- 2 x — 类型 2 的事件,编号为 x 的展品已被移除;保证被移走的展品当时已经展出
- 3 — 类型 3 的事件,Kleofáš 参观博物馆并提出问题
最多有 10 000 个类型 1 事件和至少一个类型 3 事件。
输出
由于值 s(m) 的数量可能会变大,因此以特殊格式输出类型 3 事件的答案。
对于类型 3 的每个事件,考虑针对 Kleofáš 在此事件中提出的问题计算的值 s(m);打印包含单个数字的一行
$$\sum_{m=1}^{k} s(m) \cdot p^{m-1} \mod q$$
其中 p = 107 + 19,q = 109 + 7。
按照类型 3 事件在输入中出现的顺序打印它们的答案。
示例
输入 #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
注意
在第一个示例中,类型 3 的各个事件的显示展品数量和值 s(1), ..., s(10) 按顺序为:
$$\text{展示} 1,2,3; \quad (s(1),\ldots,s(10))=(5,5,5,30,35,60,65,65,90),$$
$$\text{展示} 1,2,3,4,5; \quad (s(1),\ldots,s(10))=(5,5,20,30,42,60,65,65,80,90),$$
$$\text{展示} 1,3,5; \quad (s(1),\ldots,s(10))=(5,5,20,30,35,35,50,55,55)$$
$$\text{展示} 1,3,5,6; \quad (s(1),\ldots,s(10))=(5,5,20,30,35,40,50,55,60,70).$$
单个展品的值为 v1 = 30、v2 = 60、v3 = 5、v4 = 42、v5 = 20、v6 = 40,其质量为 w1 = 4、w2 = 6、w3 = 1、w4 = 5、w5 = 3、w6 = 6。
在第二个示例中,在删除所有展品后询问唯一的问题,因此对于任何 m,s(m) = 0。