#2661 개미

1 s   128 MB  

Description

길이가 L cm인 터널 위에 n 마리의 개미가 존재한다. 이들은 모두 왼쪽, 혹은 오른쪽으로만 이동한다.

그러나, 다른 개미와 부딪히면, 반대 방향으로 이동한다.

개미가 터널의 끝에 도달하면, 터널을 나간다.

모든 개미가 터널을 나가기 위한 최소의 시간을 구하라

(단, 개미는 1초에 1m씩 움직 인다.)

Input

테스트 케이스가 들어온다.

터널의 길이($1 \leq L \leq 10^6$)와, 개미의 수($1 \leq N \leq 10^6$)가 들어온다.

개미의 위치와, 방향이 들어온다.

Output

테스트 케이스 마다 모든 개미가 터널을 나가기 위한 최소의 시간을 구하라

Sample Input

Sample Output

1
10 3
3 R
5 L 
8 L
8