개미의 이동

$A$마리의 개미가 일직선 모양의 나무 판자 위에서 행진하고 있다. 각 개미는 왼쪽 또는 오른쪽 중 한 방향을 바라보며, 바라보는 방향으로 1초에 1cm씩 전진한다.

• 두 개미가 같은 지점에서 만나면, 두 개미는 즉시 방향을 바꾸어 서로 반대 방향으로 전진한다.
• 개미가 판자의 양 끝(위치 $0$ 또는 위치 $L$)에 도달하면 땅으로 떨어지며, 그 이후로는 다른 개미에게 아무런 영향을 주지 않는다.
• 개미의 크기는 무시한다.

예를 들어(원문에는 이 상황을 나타내는 그림이 함께 주어졌다), 시각 $0$에서 시작하여 $1$초 후 개미 E와 A가 위치 $2$에서 만나 서로 방향을 바꾼다. $1.5$초 후에는 A와 B가 만남과 동시에 C와 D도 만나 네 개미가 모두 방향을 바꾼다. 다시 $0.5$초 후(즉 시각 $3$초)에 개미 E가 판자 끝에 도달하여 땅으로 떨어진다.

개미들의 움직임을 시뮬레이션하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫째 줄에는 판자의 길이 $L$(단위: cm, $1 \le L \le 99999$)과 개미의 수 $A$($1 \le A \le L+1$)가 주어진다.

이어지는 $A$개의 줄에는 각 개미의 위치 $X_i$($0 \le X_i \le L$)와 바라보는 방향(L: 왼쪽, R: 오른쪽)이 주어진다. 서로 다른 두 개미가 같은 위치에 있는 경우는 없다.

입력은 파일의 끝까지 계속된다.

각 테스트 케이스마다 다음 형식의 문장을 한 줄에 출력한다.

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

여기서 $T$는 마지막 개미가 떨어진 시각이고, $P$는 그 개미가 시각 $0$에 있던 처음 위치이다. 만약 두 개미가 동시에 떨어진다면 started at P 대신 started at P and Q를 출력한다. 이때 $P < Q$이다.