Description

小 Y 非常有钱，所以她可以买下所有她想要的东西。

今天，她来到商店购物。商店有 $n$ 件商品，第 $i$ 件商品的价格为 $v_i$，性价比为 $w_i$。一开始，小 Y 会买下性价比最大的所有商品（如果有多个就全部买下）。接下来，有 $m$ 个事件依次发生，第 $i\;(1 \leq i \leq m)$ 个事件可能为以下两种类型之一：

1. 新增一件价格为 $x_i$，性价比为 $y_i$ 的商品，其编号为 $n+i$；
2. 将编号为 $x_i$ 的商品的性价比更改为 $y_i$。

请注意，一旦小 Y 买下了某件商品，之后即使这件商品的性价比降低，小 Y 也不会出售这件商品。

每次事件后，计算小 Y 已买下商品中的最低性价比 $L$，小 Y 会在此时买下所有性价比 $\ge L$ 的未被购买的商品。

作为小 Y 的生活助理，你需要统计每次事件后小 Y 的总花销。

Input Format

第一行，两个整数 $n, m$，分别表示商品数与事件数。

接下来 $n$ 行，第 $i$ 行包含两个整数 $v_i, w_i$。

接下来 $m$ 行，第 $i$ 行包含三个整数 $o_i, x_i, y_i$，其中 $o_i = 1$ 表明事件 $i$ 是新增商品事件，$o_i = 2$ 表明事件 $i$ 是修改性价比事件。

Output Format

输出共 $m$ 行。第 $i$ 行包含一个整数，表示事件 $i$ 后小 Y 的总花销。

6 4
1 1
1 2
1 3
1 4
1 5
1 5
2 5 4
1 10 3
2 8 4
2 5 2

3
3
13
15

5 5
11 4
13 6
14 3
20 8
0 5
2 4 5
2 5 0
2 4 10
1 12 2
2 1 0

33
58
58
70
70

Hint

样例解释 1

初始，编号为 $5, 6$ 的商品性价比最高，因此所有小 Y 购买的商品为 $\{5, 6\}$。

事件 $1$ 中，商品 $5$ 的性价比被修改为 $4$。此时有 $w_4 \geq w_5$，因此小 Y 购买商品 $4$，而其余商品仍未被购买。此时所有小 Y 购买的商品为 $\{4, 5, 6\}$。

事件 $2$ 中，新增了一件商品，其编号为 $6+2=8$，但其性价比只有 $3$，因此小 Y 没有购买它。

事件 $3$ 中，商品 $8$ 的性价比被修改为 $4$，此时小 Y 购买商品 $8$，现在所有她购买的商品为 $\{4, 5, 6, 8\}$。

事件 $4$ 中，商品 $5$ 的性价比被修改为 $2$，最终所有小 Y 购买的商品为 $\{2, 3, 4, 5, 6, 8\}$。

数据范围

对于所有数据：保证 $1 \leq n \leq 2\times 10^5$，$1 \leq m \leq 2\times 10^5$，$0 \leq v_i, w_i, y_i \leq 10^9$，$o_i \in \{1, 2\}$。若 $o_i = 1$，则 $0 \leq x_i \leq 10^9$，否则保证编号为 $x_i$ 的商品已经存在。