高山游乐园（Mountain Amusement Park）新开了一款全新的模拟过山车。模拟轨道由 $n$ 段首尾相接的铁轨组成，第一段铁轨的起点固定在高度 $0$ 处。操作员 Byteman 可以通过调整若干连续铁轨的高度变化来任意重新配置轨道。其他铁轨的高度变化不受影响。每次调整铁轨时，后面的轨道会相应地升高或降低，以保持轨道的连接，同时起点仍保持在高度 $0$。下图展示了两个轨道重新配置的例子。

每次运行过山车时，车子会被发射，并具有足够的能量达到高度 $h$。也就是说，只要轨道的高度不超过 $h$，且没有到达轨道末端，车子就会继续行驶。

给定一天中所有运行记录和轨道配置修改记录，计算每次运行中车子在停止前通过的铁轨数量。

在模拟器内部，轨道被表示为由 $n$ 个高度变化组成的序列，每段铁轨对应一个。第 $i$ 个数字 $d_i$ 表示第 $i$ 段铁轨的高度变化（单位：厘米）。假设在通过 $i-1$ 段铁轨后，车子达到了 $h$ 厘米的高度。在通过 $i$ 段铁轨后，车子将达到 $h + d_i$ 厘米的高度。

最初，铁轨是水平的；即对于所有 $i$，都有 $d_i = 0$。运行和重新配置在一天中交替进行。每次重新配置由三个数字 $a$、$b$ 和 $D$ 指定。要调整的区间由铁轨 $a$ 到 $b$（含）组成。该区间内每段铁轨的高度变化被设置为 $D$。即对于所有 $a \le i \le b$，有 $d_i = D$。

每次运行由一个数字 $h$ 指定——车子可以达到的最大高度。

任务

编写一个程序：

• 从标准输入读取一系列交替进行的重新配置和运行操作，
• 对于每次运行，计算车子通过的铁轨数量，
• 将结果写入标准输出。

输入格式

输入的第一行包含一个正整数 $n$——铁轨的数量，$1 \le n \le 1\,000\,000\,000$。

接下来的行包含交替进行的重新配置和运行操作，最后以结束标记结束。每行包含以下内容之一：

• 重新配置——单个字母 I，以及整数 $a$、$b$ 和 $D$，全部由单个空格分隔（$1 \le a \le b \le n$，$-1\,000\,000\,000 \le D \le 1\,000\,000\,000$）。
• 运行——单个字母 Q，以及一个整数 $h$（$0 \le h \le 1\,000\,000\,000$），由单个空格分隔。
• 单个字母 E——结束标记，表示输入数据的结束。

你可以假设在任何时刻，轨道上任意一点的高度都在区间 $[0, 1\,000\,000\,000]$ 厘米内。输入不超过 $100\,000$ 行。

输出格式

输出的第 $i$ 行应包含一个整数——车子在第 $i$ 次运行期间通过的铁轨数量。

数据范围

• 在 $50\%$ 的测试用例中，$n$ 满足 $1 \le n \le 20\,000$，且输入不超过 $1\,000$ 行。
• 对于所有测试用例，$1 \le n \le 1\,000\,000\,000$，输入不超过 $100\,000$ 行。

样例

输入样例 1

4
Q 1
I 1 4 2
Q 3
Q 1
I 2 2 -1
Q 3
E

输出样例 1

4
1
0
3

说明

每次重新配置前后轨道的示意图。x 轴表示铁轨编号。y 轴和点上方的数字表示高度。线段上方的数字表示高度变化。