Kile 是萨格勒布一家著名餐厅的主厨。最近他辞职了，去 Malnar 先生的甜品店做了一名烘焙师，因为 Malnar 先生的店确实是最好的。而且，甜点一直是他最喜欢的食物。

上班第一天，厨房里有一张桌子，上面放着 $n$ 个盘子，第 $i$ 个盘子里有 $A_i$ 个顶级蛋糕。Kile 准备好开始工作了，但他没有意识到一个关键问题：在处理这些甜点时，他时不时会感到饥饿。

每一分钟，他都会执行以下三种操作之一：

• ISPECI x y：在第 $x$ 个盘子上增加 $y$ 个新蛋糕。
• POJEDI x y：Kile 太饿了，他从第 $x$ 个盘子上拿走并吃掉了 $y$ 个蛋糕。
• POSLUZI y：将所有至少有 $y$ 个蛋糕的盘子从厨房移走并提供给客人。

盘子不会被放回厨房，盘子的索引保持不变。Kile 想知道在每次 POSLUZI 操作中，有多少个盘子被移出了厨房。请帮助他回答在接下来的 $q$ 分钟内的问题。

输入格式

第一行包含自然数 $n$ ($1 \le n \le 10^5$) 和 $q$ ($1 \le q \le 10^5$)。

第二行包含 $n$ 个整数，其中第 $i$ 个数表示 $a_i$ ($0 \le a_i \le 10^9$)。

接下来的 $q$ 行描述了发生的事件。

如果第 $i$ 个事件是 ISPECI，则该行包含数字 $x$ ($1 \le x \le n$) 和 $y$ ($0 \le y \le 10^9$)。

如果第 $i$ 个事件是 POJEDI，则该行包含数字 $x$ ($1 \le x \le n$) 和 $y$ ($0 \le y \le 10^9$)。保证 Kile 能成功完成所有 POJEDI 事件，即第 $x$ 个盘子中始终至少有 $y$ 个蛋糕。

如果第 $i$ 个事件是 POSLUZI，则该行包含数字 $y$ ($0 \le y \le 10^9$)。

输出格式

对于每个 POSLUZI 查询，输出被移出的盘子数量。同时，对于每个 POSLUZI 查询，输出被移出的蛋糕总数。

样例

输入格式 1

6 7
2 5 0 3 7 1
POSLUZI 6
ISPECI 3 4
POJEDI 2 2
ISPECI 1 3
POSLUZI 4
POSLUZI 3
ISPECI 6 4

输出格式 1

1 7
2 10
2 8

输入格式 2

4 6
1 2 6 2
ISPECI 2 2
POSLUZI 3
POJEDI 1 1
POSLUZI 1
ISPECI 1 3
POSLUZI 4

输出格式 2

2 10
1 1
0 0