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 ci , which determines the number of trees it can be applied to. Moreover, for each bottle there is a minimal height hi 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 ci smallest trees chosen from the trees that are at least hi 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.

입력

• The first line of the standard 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 ti (ti = F or ti = C), which describes the type of the task.

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

  If ti = C then two integers mini and maxi follow. They denote that Egon has to compute the number of trees whose height H is between mini and maxi centimeters (mini H maxi).

출력

Constraints

• 1 <= N,M <= 100 000
• 1 <= ci <= N, 0 <= hi <= 1 000 000 000
• 1 <= mini <= maxi <= 1 000 000 000.

입출력 예

입력

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

출력

3
0
5

출처:BOI 2011 day1 1/4