Mun, Hong, An

Interview

Time limit2sMemory limit256 MB

Summary

Each secretary adds one step to every stone in one direction from the start. Count total steps per stone modulo 3, then split P by the final blue, red, and green counts.

Level: Easy3 of 10
Topics: Implementation, Prefix sum, Simulation, Math
Solved: No attempts yet

Problem

A valley in Daehan village has a stepping stone bridge built from 100 stones in a row. The stones were ordinary until Choe Son-sil, the village shaman, cursed them, and now a stone changes color every time someone steps on it. Each stone is blue, red or green. Stepping on a blue stone turns it red, stepping on a red stone turns it green, and stepping on a green stone turns it blue again. The stones are numbered from 1 at the left end of the bridge up to 100 at the right end.

Kim Geu-ne lives in Daehan village and has three sons. The eldest, Mun Ju-in, likes blue. The second, Hong Ji-pyo, likes red. The youngest, An Cheong-so, likes green.

Kim Geu-ne could not settle on a way to divide the estate, then remembered the bridge in the valley and made up his mind. The next day he placed N secretaries on the stones, one secretary per stone, and had each of them face either left or right. At the moment the secretaries first stand on the stones, all 100 stones are blue.

When Kim Geu-ne shouts "Start!", each of the N secretaries crosses to the next stone in the direction they face, once per second. The stones are wide enough that several secretaries can pass over one stone at the same time. A secretary who has left the bridge steps on no further stone.

After every secretary has crossed the bridge, let a, b and c be the numbers of blue, red and green stones that remain. Kim Geu-ne passes the estate to his three sons in the ratio a to b to c. How much does each son inherit?

Input

The first line contains an integer P, the estate of Kim Geu-ne (0 ≤ P ≤ 290,000). The second line contains the number of secretaries N (0 ≤ N ≤ 100). Each of the next N lines contains the position and the direction of one secretary, separated by a space. The position is a stone number between 1 and 100, and the direction is 'L' for left or 'R' for right. No two secretaries start on the same stone. After the start several secretaries can arrive on one stone at the same time, and each of them counts as one step on that stone.

Output

Print the amounts inherited by Mun Ju-in, Hong Ji-pyo and An Cheong-so, in that order, one per line. Print each amount with exactly two digits after the decimal point. All three amounts are exact at two decimal places.

Hint

The final color of a stone depends only on how many times it was stepped on. Take that count modulo 3: a remainder of 0 leaves the stone blue, 1 makes it red, and 2 makes it green. A secretary facing right who starts on stone i steps once on each stone from i+1 to 100, and a secretary facing left steps once on each stone from 1 to i-1.

Examples5

Example 1

Input

Expected output

26000.00
34000.00
40000.00

Example 2
Input
```
0
3
60 R
25 L
50 R
```
Expected output
```
0.00
0.00
0.00
```
Example 3
Input
```
290000
0
```
Expected output
```
290000.00
0.00
0.00
```
Example 4
Input
```
12345
2
1 L
100 R
```
Expected output
```
12345.00
0.00
0.00
```
Example 5
Input
```
100
1
1 R
```
Expected output
```
1.00
99.00
0.00
```