← 返回题目列表

Codeforces · 601/E

E. 博物馆抢劫案

中文机器翻译题面 查看原题

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。