题意翻译

初始有 $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$

### 题意翻译

初始有 $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$