bee 2529 - Flea Circus

Vasya and Petya decided to invest in a new enterprise. They opened a flea circus.

Right now, they are rehearsing with their P fleas in a straight line. Each flea holds a small board with an integer written on it, and can follow 4 different orders:

Replace the number on its board by another given one;
Yell the number of even integers on boards held by fleas in a given interval;
Yell the number of odd integers on boards held by fleas in a given interval;
Start dancing while the fleas in a given interval reverse the order of their boards.

Some fleas did not understand the last order and asked for an example. Vasya then said:

Consider there are 10 fleas holding, initially, boards with the following integers:

70, 15, 3, 4, 15, 59, 0, 1, 444, 2

If they receive the order to reverse the order of the boards in the interval [3, 7], then the new line will be:

70, 15, 0, 59, 15, 4, 3, 1, 444, 2

The duo asked you to write a program to simulate the rehearsing, so they can see if they are well trained.

Input

The input contains several test cases. In each test case, the first line contains two integers P and Q (1 ≤ P, Q ≤ 10⁵). The following line contains P integers p_i (0 ≤ p_i ≤ 10⁹), the integers initially written on the fleas’ boards.

Next Q lines describe the orders they receive. Each order may be:

S a v: Replace the integer on the board held by the flea at position a (1 ≤ a ≤ P) by v;
E a b: Yell the number of even integers on boards held by fleas in the interval [a,b] (1 ≤ a ≤ b ≤ P);
O a b: Yell the number of odd integers on boards held by fleas in the interval [a,b] (1 ≤ a ≤ b ≤ P);
I a b: Reverse the order of the boards in the interval [a, b] (1 ≤ a ≤ b ≤ P).

The input ends with end-of-file (EOF).

Output

For each test case, print a line with the value that must be yelled for each order that requires an yell (E and O).

Input Sample	Output Sample
7 8 30 50 1 2 3 4 10 O 1 7 S 2 7 E 1 7 S 3 8 O 1 7 O 1 3 I 3 5 O 1 3	2 4 2 1 2