题目描述

儿童节即将到来。在这一天，小朋友们会得到好多糖果。在 MAX 城市，人们发明了一种糖果自动管理系统（ACM 系统），该系统能管理 $N$ 堆糖果。系统只能执行两种操作：

• I a b c，ACM 将在堆 $a$ 至堆 $b$ 之间（包含 $a$ 和 $b$）每堆糖果加 $c$ 个。
• C a b，ACM 将会选择 $a$ 到 $b$ 堆之间糖果数最多的那堆糖果送给一个小朋友。如果有两堆或两堆以上糖果数为最大值，选择那么编号小的那堆。操作完毕后选择的堆清空。

给出一系列的操作，对于每个 C 操作，输出堆的糖果数。

输入格式

有多组测试数据。

每组测试数据的第一行为两个整数 $N,M$，$N$ 表示糖果堆的数目，$M$ 表示操作的次数。

下来 $M$ 行，每行为一个操作。

输入当 $N=M=0$ 时结束，并且不做任何处理。

初始时，所有堆糖果数目为 $0$。

输出格式

对于每个 C 操作，输出小朋友能得到的糖果的数目。

5 4
I 1 5 1
C 2 3
I 2 2 4
C 2 3
0 0

1
4

数据规模与约定

$0<N,M\le 10^5,1\le a\le b\le N,0<c\le 100$。