题目描述

游乐园已经开始运行一个崭新的模拟过山车。模拟的轨道由 $n$ 段铁轨组成，并且首尾相连。第一段铁轨从高度 $0$ 开始。

操作员 Byteman 能通过调整连续几段的铁轨高度来改造这条轨道。在被改造的一段前面的铁轨高度不受影响。 每一次铁轨被调整。后面的轨必须升起或降低来保持连通，并保证起点高度为 $0$。下页举例说明轨道改造过程。 每次开始时车都有足够能量到达高度 $h$。也就是说，只要轨道的高度不超过 $h$，车就一直开下去, 甚至直到结束。

给出每天的运行和改造情况, 为每次运行计算在车停止前，到达的铁轨数。铁轨以一个 $n$ 个数的数列形式表示 ，一个数对应一段铁轨。第 $i$ 个 $d_i$ 表示在第 $i$ 段铁轨上的高度变化。也就是说，在到达铁轨 $i$ 前，如果车的高度是 $h$，那么经过铁轨i后，高度变为 $h+d_i$。

最初轨道是一条水平线。就是说对于所有的 $i$ 都是 $d_i=0$。运行和改造交错进行。 每个改造用三个数表示: $a$ ，$b$ 和 $D$。表示从 $a$ 到 $b$ (包括 $a$,$b$) 的所有 $d_i$ 改为 $d_i=D$。每次运行给定一个数字 $h$ ——车能到达的最大高度。

输入格式

输入的第一行包括一个正整数 $n$ ——铁轨的数目。

下面的行包括改造和运行，各有一个标识符：

• 改造——一个字母 I，和整数$a$,$b$,$D$ ,中间用一个空格隔开。
• 运行——一个字母 Q，和一个整数 $h$，用一个空格隔开。
• 一个字母 E ——结束符号，表示输入结束。

你可以假设任意时刻任意铁轨的高度在 $[1，1000000000]$ 区间内。

输入不超过 $10000$ 行。

输出格式

第 $i$ 行需包含一个整数， 即第 $i$ 次运行经过的铁轨数。

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

4
1
0
3

提示

对于 $50\%$ 的数据，$1 \le n \le 2 \times 10^4$，且输入不超过 $1000$ 行；

对于 $100\%$ 的数据，$1 \le n \le 10^9$，$1 \le a,b \le n$，$- 10^9 \le D \le 10^9$，$0 \le h \le 10^9$。