The Last Ant

A straight tunnel with no branches is crowded with busy ants coming and going. Some ants walk left to right and others right to left. Every ant walks at a constant speed of 1 cm/s.

When two ants meet, they try to pass each other. Some sections of the tunnel are narrow, and two ants cannot pass each other there. When two ants meet at a narrow section, both turn around and start walking in the opposite direction. An ant that reaches either end of the tunnel leaves the tunnel.

The tunnel has an integer length in centimeters. Every narrow section of the tunnel is an integer number of centimeters from both ends. Away from those sections the tunnel is wide enough for two ants to pass each other. All ants start walking at distinct narrow sections. No ant newly enters the tunnel, so every ant inside it eventually leaves. Write a program that reports which ant is the last to leave the tunnel and when it leaves.

Figure 1 shows how the ants move during the first two seconds in a tunnel 6 centimeters long. Initially three ants, numbered 1, 2, and 3, start walking at narrow sections 1, 2, and 5 centimeters from the left end. After 0.5 seconds ants 1 and 2 meet at a wide section and pass each other. Two seconds after the start, ants 1 and 3 meet at a narrow section and turn around.

Figure 1 corresponds to the first dataset of the first example.

Figure 1. Movements of ants

The input consists of one or more datasets. Each dataset is formatted as follows.

n l
d1 p1
d2 p2
.
.
.
dn pn

The first line of a dataset contains two integers separated by a space. $n$ ($1 \le n \le 20$) is the number of ants, and $l$ ($n + 1 \le l \le 100$) is the length of the tunnel in centimeters. The following $n$ lines describe the initial states of the ants. Each of those lines has two items, $d_i$ and $p_i$, separated by a space. The ants are numbered 1 through $n$. Ant $i$ has initial direction $d_i$ and initial position $p_i$. The initial direction $d_i$ ($1 \le i \le n$) is L (to the left) or R (to the right). The initial position $p_i$ ($1 \le i \le n$) is an integer giving the distance from the left end of the tunnel in centimeters. The ants are listed in left to right order, so $1 \le p_1 < p_2 < \cdots < p_n \le l - 1$.

The last dataset is followed by a line containing two zeros separated by a space.

For each dataset, print one line with how many seconds it takes before all the ants leave the tunnel and the number of the ant that leaves last, separated by a single space. If two ants leave at the same time, print the number of the ant that leaves through the left end of the tunnel.