在一家苏联餐厅门前，有 $N$ 个人排队等待餐厅开门。这些人按到达顺序被标记为从 $1$ 到 $N$ 的自然数。菜单上只有一种选择，即“招牌菜”煎蛋。餐厅里没有厨师，客人们必须自己准备餐点。餐厅里只有一口平底锅，因此在任何时刻最多只能有一位客人准备食物。此外，餐厅里只有一把叉子和一把刀，因此在任何时刻最多只能有一位客人进食。幸运的是，餐厅里有无限多的盘子，所以准备好食物的客人可以将食物转移到盘子上，等待叉子和刀空闲。

对于每位客人，已知其准备食物所需的时间以及进食所需的时间。你的任务是确定如果客人们选择以最优顺序准备和进食，所有人吃完饭所需的最短时间。

此外，在餐厅开门之前，发生了 $K$ 个关键事件，类型如下：

• DOLAZI a b：来了一位新客人，他准备食物需要 $a$ 分钟，进食需要 $b$ 分钟。新来的客人被标记为尚未被任何现有客人使用的最小自然数。
• ODLAZI x：第 $x$ 个到达餐厅的客人离开了。
• POREDAK：客人们很焦急，想知道以什么顺序准备和进食，才能使所有人吃完饭的总时间最短。

在第一个事件发生前，你需要输出 $N$ 位客人吃完饭所需的最短时间。对于每个 DOLAZI 或 ODLAZI 事件，你需要输出该事件发生后，餐厅门前剩余的客人群体吃完饭所需的最短时间。最后，在每个 POREDAK 事件后，你需要输出以什么顺序准备和进食，才能使当前门前的客人群体在最短时间内全部吃完。

输入格式

第一行包含两个自然数 $N$ 和 $K$。

接下来的 $N$ 行，每行包含两个自然数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le 10^9$)，表示标记为 $i$ 的客人准备食物需要 $a_i$ 分钟，进食需要 $b_i$ 分钟。

接下来的 $K$ 行，每行包含一个如上所述的关键事件。

你可以假设事件之间是相互一致的。也就是说，离开的客人一定已经到达。此外，餐厅门前在任何时刻至少会有一位客人，且新来客人的准备和进食速度遵循前述限制。

输出格式

第一行输出初始 $N$ 位客人吃完饭所需的最短时间。

如果第 $i$ 个事件是 DOLAZI 或 ODLAZI，则在第 $(i+1)$ 行输出该事件发生后，餐厅门前客人群体吃完饭所需的最短时间。

如果第 $i$ 个事件是 POREDAK，则在第 $(i+1)$ 行输出 $2x$ 个数字，其中 $x$ 是当前门前客人的数量。前 $x$ 个数字应包含客人按准备食物顺序的标记，后 $x$ 个数字应包含客人按进食顺序的标记。

子任务

样例

样例输入 1

2 1
1 3
2 3
POREDAK

样例输出 1

7
1 2 1 2

样例输入 2

1 4
4 3
DOLAZI 3 8
DOLAZI 5 2
ODLAZI 1
ODLAZI 3

样例输出 2

7
14
16
13
11

说明

第一个样例的说明： 标记为 1 的客人开始准备餐点并在第 1 分钟结束。随后该人开始进食，同时标记为 2 的客人开始准备他的餐点。在第 3 分钟，标记为 2 的客人完成了准备，但标记为 1 的客人尚未吃完，因此他必须等待直到第 4 分钟。最后，在第 4 分钟，标记为 2 的客人开始进食，并在第 7 分钟结束。