Baltic Olympiad in Informatics: 2011 Day 1, Problem 1

Egon takes care of a garden with ~N~ apple trees. His responsibilities include two types of tasks: fertilizing the trees and computing some statistics about them. For fertilizing the trees he has several bottles of MegaBoostFertilizer, which, when treated on trees, causes them to grow one centimeter up instantly.

Every bottle has a limited capacity ~c_i~, which determines the number of trees it can be applied to. Moreover, for each bottle there is a minimal height ~h_i~ of trees, which can be treated with it. Since Egon wants to have all his trees as big as possible, he always applies the fertilizer to the ~c_i~ smallest trees chosen from the trees that are at least ~h_i~ centimeters high.

When Egon computes statistics about trees he has to determine the number of trees whose height is in some given interval. Egon is quite busy working in the garden, so he asked you to write a program, that given the list of his tasks, computes the statistics for him.

Constraints

~1 \le N, M \le 10^5~

~1 \le c_i \le N~

~0 \le h_i \le 10^9~

~1 \le min_i \le max_i \le 10^9~

Subtask 1 [30%]

~1 \le N \le 7\,000~

The number of type F tasks is at most ~7\,000~.

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line of input contains two integers ~N~ and ~M~ denoting the number of trees in Egon's garden and the number of his tasks.

The second line contains a sequence of ~N~ integers from the range ~[1, N]~ describing the initial heights of the trees in centimeters.

The following ~M~ lines describe the tasks in chronological order. Each of those lines begins with a character ~t_i~ (~t_i =~ F or ~t_i =~ C), which describes the type of the task.

If ~t_i =~ F then two integers ~c_i~ and ~h_i~ follow. Such a line means that Egon applies a bottle of MegaBoostFertilizer to the ~c_i~ smallest trees that are at least ~h_i~ centimeters high. When there are less than ~c_i~ trees of sufficient height, he applies the fertilizer to all such trees and discards the bottle with some fertilizer remaining.

If ~t_i =~ C then two integers ~min_i~ and ~max_i~ follow. They denote that Egon has to compute the number of trees whose height ~H~ is between ~min_i~ and ~max_i~ centimeters ~(min_i \le H \le max_i)~.

Output Specification

For every task of type C, output one line containing the number of apple trees that have the required height. The order of the results should conform to the order of type C tasks in the input.

Sample Input

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

Sample Output

3
0
5