마지막 개미

갈림길이 없는 곧은 굴을 개미가 바쁘게 오간다. 왼쪽에서 오른쪽으로 걷는 개미도 있고, 오른쪽에서 왼쪽으로 걷는 개미도 있다. 모든 개미는 초당 1cm의 일정한 속력으로 걷는다.

두 개미가 만나면 서로 지나쳐 가려고 한다. 그런데 굴에는 폭이 좁아 두 개미가 비켜 갈 수 없는 지점이 있다. 좁은 지점에서 두 개미가 만나면 둘 다 몸을 돌려 반대 방향으로 걷기 시작한다. 개미는 굴의 양쪽 끝 중 한쪽에 닿으면 굴을 떠난다.

굴의 길이는 정수 cm이다. 좁은 지점은 모두 굴의 양쪽 끝에서 정수 cm 떨어져 있고, 그 지점을 뺀 나머지 구간은 두 개미가 비켜 갈 만큼 넓다. 모든 개미는 서로 다른 좁은 지점에서 걷기 시작한다. 굴에 새로 들어오는 개미는 없다. 따라서 굴 안의 개미는 언젠가 모두 굴을 떠난다. 굴을 마지막으로 떠나는 개미가 몇 번이고 그때가 언제인지 구하는 프로그램을 작성하라.

그림 1은 길이가 6cm인 굴에서 개미가 처음 2초 동안 어떻게 움직이는지 보여 준다. 처음에 1번, 2번, 3번 개미가 왼쪽 끝에서 각각 1cm, 2cm, 5cm 떨어진 좁은 지점에서 걷기 시작한다. 0.5초 후 1번과 2번 개미가 넓은 구간에서 만나 서로 지나쳐 간다. 출발한 지 2초 후에는 1번과 3번 개미가 좁은 지점에서 만나 몸을 돌린다.

그림 1은 첫 번째 예제의 첫째 데이터셋에 해당한다.

그림 1. 개미의 움직임

입력은 데이터셋 하나 이상으로 이루어진다. 각 데이터셋의 형식은 다음과 같다.

n l
d1 p1
d2 p2
.
.
.
dn pn

데이터셋의 첫 줄에는 정수 두 개가 공백으로 구분되어 주어진다. $n$ ($1 \le n \le 20$)은 개미의 수이고, $l$ ($n + 1 \le l \le 100$)은 굴의 길이를 cm 단위로 나타낸다. 이어지는 $n$개의 줄에는 개미의 초기 상태가 주어진다. 각 줄에는 $d_i$와 $p_i$ 두 항목이 공백으로 구분되어 주어진다. 개미에는 1번부터 $n$번까지 번호가 붙는다. $i$번 개미의 초기 방향은 $d_i$, 초기 위치는 $p_i$이다. 초기 방향 $d_i$ ($1 \le i \le n$)는 왼쪽을 뜻하는 L 또는 오른쪽을 뜻하는 R이다. 초기 위치 $p_i$ ($1 \le i \le n$)는 굴의 왼쪽 끝에서 떨어진 거리를 cm 단위로 나타낸 정수이다. 개미는 왼쪽에서 오른쪽 순서로 나열되므로 $1 \le p_1 < p_2 < \cdots < p_n \le l - 1$이다.

마지막 데이터셋 다음 줄에는 0 두 개가 공백으로 구분되어 주어진다.

각 데이터셋마다 모든 개미가 굴을 떠나기까지 걸리는 시간을 초 단위로, 그리고 마지막으로 떠나는 개미의 번호를 공백 하나로 구분해 한 줄에 출력한다. 두 개미가 같은 시각에 떠나면 굴의 왼쪽 끝으로 떠나는 개미의 번호를 출력한다.