URI Online Judge | 2529

# Flea Circus

By Flávio Zavan, UFPR Brazil

Timelimit: 2

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 ≤ 105). The following line contains P integers pi (0 ≤ pi ≤ 109), 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 ≤ aP) by v;
• E a b: Yell the number of even integers on boards held by fleas in the interval [a,b] (1 ≤ abP);
• O a b: Yell the number of odd integers on boards held by fleas in the interval [a,b] (1 ≤ abP);
• I a b: Reverse the order of the boards in the interval [a, b] (1 ≤ abP).

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