CF601E 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

输入 #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

输入 #2

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

输出 #2

0

说明/提示

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