Egon 照料着一个有 $N$ 棵苹果树的花园。他的工作包括两类任务：给树施肥和统计树木的数据。

为了给树施肥，他有几瓶 MegaBoostFertilizer。当对树使用时，它能让树瞬间长高 $1$ 厘米。每瓶肥料都有一个容量限制 $c_i$，决定了它最多可以施用于多少棵树。此外，每瓶肥料还有一个最低高度限制 $h_i$，只有高度至少为 $h_i$ 厘米的树才能使用它。由于 Egon 希望所有的树都尽可能高，他总是将肥料施用于高度至少为 $h_i$ 厘米的树中高度最小的 $c_i$ 棵树。

当 Egon 统计树木数据时，他需要确定高度在某个给定区间内的树木数量。Egon 在花园里非常忙碌，因此他请求你编写一个程序，在给定他的任务列表的情况下，为他计算这些统计数据。

输入格式

输入的第一行包含两个整数 $N$ 和 $M$，分别表示 Egon 花园中的树木数量和他的任务数量。

第二行包含一个由 $N$ 个范围在 $[1, N]$ 内的整数组成的序列，描述树木的初始高度（单位：厘米）。

接下来的 $M$ 行按时间顺序描述任务。每行开头包含一个字符 $t_i$（$t_i = \text{F}$ 或 $t_i = \text{C}$），表示任务的类型。

• 如果 $t_i = \text{F}$，则后面跟着两个整数 $c_i$ 和 $h_i$。这表示 Egon 将一瓶 MegaBoostFertilizer 施用于高度至少为 $h_i$ 厘米的树中高度最小的 $c_i$ 棵树。如果满足高度要求的树少于 $c_i$ 棵，他会将肥料施用于所有这些满足要求的树，并丢弃还剩有肥料的瓶子。
• 如果 $t_i = \text{C}$，则后面跟着两个整数 $min_i$ 和 $max_i$。这表示 Egon 需要计算高度 $H$ 在 $min_i$ 和 $max_i$ 厘米之间（$min_i \le H \le max_i$）的树木数量。

输出格式

对于每个类型为 $\text{C}$ 的任务，输出一行，包含一个整数，表示满足高度要求的苹果树数量。输出结果的顺序应与输入中类型为 $\text{C}$ 的任务的顺序一致。

数据范围

• $1 \le N, M \le 100\,000$
• $1 \le c_i \le N$，$0 \le h_i \le 1\,000\,000\,000$
• $1 \le min_i \le max_i \le 1\,000\,000\,000$

在占总分 $40$ 分的测试用例中，$1 \le N \le 7\,000$ 且类型为 $\text{F}$ 的任务数量最多为 $7\,000$。

样例

输入样例 1

5 7
1 3 2 5 2
F 2 1
C 3 6
F 2 3
C 6 8
F 2 1
F 2 2
C 3 5

输出样例 1

3
0
5