## RACETIME - Race Against Time

As another one of their crazy antics, the N (1 ≤ N ≤ 100,000) cows want Farmer John to race against the clock to answer some of their pressing questions.

The cows are lined up in a row from 1 to N, and each one is holding a sign representing a number, Ai (1 ≤ Ai ≤ 1,000,000,000). The cows need FJ to perform Q (1 ≤ Q ≤ 50,000) operations, which can be either of the following:

• Modify cow i's number to X (1 ≤ X ≤ 1,000,000,000). This will be represented in the input as a line containing the letter M followed by the space-separated numbers i and X.
• Count how many cows in the range [P, Q] (1 ≤ P ≤ Q ≤ N) have Ai ≤ X (0 ≤ X ≤ 1,000,000,000). This will be represented in the input as a line containing the letter C followed by the space-separated numbers P, Q, and X.

Of course, FJ would like your help.

### Input

The first line gives the integers N and Q, and the next N lines give the initial values of Ai. Finally, the next Q lines each contain a query of the form "M i X" or "C P Q X".

### Output

Print the answer to each 'C' query, one per line.

### Example

```Input:
4 6
3
4
1
7
C 2 4 4
M 4 1
C 2 4 4
C 1 4 5
M 2 10
C 1 3 9

Output:
2
3
4
2
```

FJ has 4 cows, whose initial numbers are 3, 4, 1, and 7. The cows then give him 6 operations; the first asks him to count the how many of the last three cows have a number at most 4, the second asks him to change the fourth cow's number to 1, etc.

Warning: large input/output data.

 < Previous 1 2 Next > mathecodician: 2017-09-20 18:01:07 Here people are talking about N*log^2(N) not passing but my NQ passed lol saurabh0605: 2017-09-17 08:07:24 Is there any tutorial for this problem? bthero_03: 2017-06-08 08:58:08 Easy problem. My complexity is N + q * sqrt(n) * log(n). secta: 2016-03-02 14:00:48 I couldn't make my N*log^2(N) pass, I used segment tree with treap in each node and added fast input but still TLE :( Junior Andrade [UNIFEI]: 2015-10-09 18:54:10 N + q*sqrt(n)*log(n) works! :) aristofanis: 2013-09-03 15:17:46 How come N*sqrt(N) gets AC, and N*lg^2(N) gets TLE? edit: learn how to calculate complexities, and you will understand why you g3t tle ez problem Last edit: 2015-03-31 06:34:57 Pushkar Mishra: 2013-04-12 17:23:57 how can an algorithm of complexity (N+Q)*log(N+Q) be TLE??!