404043: GYM101401 G Balloons (B)

Mr. Light found that some colors appear more than others, and sometimes, many balloons of the same color are adjacent. He doesn't want to cut the rope and reorder them, instead, he's going to use special light sources.

The color of the balloon changes the first time it is in the range of a light source. Red balloons become blue, green balloons become red, and blue balloons become green.

After the first light source hits it, the color of the balloon never changes again -it will stay in its new color even if another light source hits it. More formally, the color of the balloon changes at most once.

Mr. Light will start turning some lights on, one by one. Each time he wants to know for each color the number of balloons with that color.

The first line of input contains two space-separated integers N, M (1 ≤ N ≤ 2 × 10⁵) , the number of balloons and the number of light sources Mr. Light will turn on.

The second line of input contains a string S of length N, representing the balloons in the line. Each letter is either 'R', 'G', or 'B' and represents the color of that balloon.

Each of the following M lines contains two space-separated integers l, r (1 ≤ l ≤ r ≤ N), representing the range of a light source.

Print M lines, the K^th line contains three integers R G B, each integer is equal to the number of balloons that appear in that color after turning on the first K light sources.

8 4
RRGRGRRB
1 3
5 8
2 2
2 7

4 1 3
3 1 4
3 1 4
2 1 5

6 3
RGRGBB
1 3
2 4
2 5

1 1 4
2 0 4
2 1 3