Ant Movement

Time limit1sMemory limit128 MB

Summary

Simulate ants that reverse on collision and fall off the plank, and report the fall time and the original position(s) of the last ants.

Level: Medium6 of 10
Topics: Simulation, Sorting, Math, Implementation
Solved: No attempts yet

Problem

$A$ ants are marching on a straight wooden plank. Each ant faces either left or right and moves 1 cm per second in the direction it faces.

When two ants meet at the same point, both immediately reverse direction and move the opposite way.
When an ant reaches either end of the plank (position $0$ or position $L$ ), it falls to the ground and no longer affects any other ant.
The size of an ant is negligible.

For example (the original statement came with a figure of this situation), starting at time $0$ : after $1$ second ants E and A meet at position $2$ and reverse direction. After $1.5$ seconds A and B meet while C and D also meet, so all four ants reverse. After another $0.5$ second (i.e. at time $3$ seconds) ant E reaches the end of the plank and falls to the ground.

Write a program that simulates the movement of the ants.

Input

The input consists of several test cases. The first line of each test case contains the length of the plank $L$ (in cm, $1 \le L \le 99999$ ) and the number of ants $A$ ( $1 \le A \le L+1$ ).

Each of the following $A$ lines contains an ant's position $X_i$ ( $0 \le X_i \le L$ ) and the direction it faces (L: left, R: right). No two ants share the same position.

The input continues until the end of the file.

Output

For each test case, print one line in the following format:

The last ant will fall down in T seconds - started at P.

Here $T$ is the time at which the last ant fell, and $P$ is the position where that ant was located at time $0$ . If two ants fall at the same time, print started at P and Q instead of started at P, where $P < Q$ .

Examples3

Example 1

Input

Expected output

The last ant will fall down in 90000 seconds - started at 0.
The last ant will fall down in 0 seconds - started at 0.
The last ant will fall down in 13 seconds - started at 6 and 8.

Example 2

Input

5 2
0 R
5 L

Expected output

The last ant will fall down in 5 seconds - started at 0 and 5.

Example 3

Input

20 2
5 R
15 L

Expected output

The last ant will fall down in 15 seconds - started at 5 and 15.