물리 실험

웨이브 머신은 파동의 움직임을 관찰하기 위한 물리 실험 장치이다. 횡파를 발생시킬 수 있고, 발생한 파동은 일정한 속력으로 진행하며 장치의 양 끝에서 반사된다.

이 문제에서 다루는 파동은 파장이 매우 짧은 1주기 파동뿐이며, 파동의 위치는 점으로 본다. 임의의 실수 $x \ge 0$에 대해, 웨이브 머신의 왼쪽 끝에서 오른쪽으로 $x$만큼 떨어진 위치의 좌표를 $x$라고 한다. 오른쪽 끝의 좌표는 $m$이다. 왼쪽 끝에서 파동을 발생시키면 파동은 처음에 속력 $v$로 오른쪽으로 진행한다. 파동이 좌표 $m$에 도달하면 반사되어, 같은 속력으로 왼쪽으로 진행한다. 마찬가지로 파동이 좌표 $0$에 도달하면 진행 방향은 다시 오른쪽이 된다. 파동이 반사되는 곳은 양 끝뿐이다. 한번 발생한 파동은 길이 $m$의 웨이브 머신 위를 속력 $v$로 계속 왕복한다.

실험에서는 왼쪽 끝에서 파동을 발생시키고 잠시 기다렸다. 관찰을 시작한 시각 0에 파동은 좌표 $x_0$에 있었고 진행 방향은 오른쪽이었다. 이후 파동의 좌표와 진행 방향을 1단위 시간마다 총 $t$번 기록했다.

그런데 시각 0의 좌표 $x_0$와 속력 $v$를 기록하지 않았다. 또한 $t$개의 기록을 뒤섞어서, 어느 기록이 어느 시각의 것인지 알 수 없게 되었다. 재실험은 피하고 싶으니, 남은 기록과 모순되지 않는 $x_0$와 $v$의 값으로 실험 보고서를 쓰려고 한다.

입력으로 웨이브 머신의 길이 $m$과 $t$개의 기록이 주어진다. 각 기록은 파동의 좌표 $y_i$와 진행 방향 $d_i$로 이루어지며, 시각 $1, \ldots, t$ 중 하나에 해당한다. 좌표 $0$에서 진행 방향은 항상 R(오른쪽), 좌표 $m$에서는 항상 L(왼쪽)이다.

아래 조건을 모두 만족하는 $x_0$와 $v$의 값을 한 쌍 구한다. 해가 여러 개라면 그중 어느 것을 출력해도 된다.

• 시각 0에서 파동의 진행 방향은 오른쪽이다.
• 시각 0에서 파동의 좌표 $x_0$는 $0$ 이상 $m-1$ 이하의 정수이다.
• 파동의 속력 $v$는 $1$ 이상 $2m$ 이하의 정수이다.
• $(1, \ldots, t)$의 순열 $(p_1, \ldots, p_t)$가 존재하여, 모든 $j$에 대해 시각 $p_j$에서 파동의 좌표는 $y_j$이고 진행 방향은 $d_j$이다.

입력은 여러 개의 데이터셋으로 이루어지며, 데이터셋의 개수는 50을 넘지 않는다. 각 데이터셋은 다음 형식으로 주어진다.

$m$ $t$ $y_1$ $d_1$ $\vdots$ $y_t$ $d_t$

제약: $1 \le m \le 10^9$, $2 \le t \le 10^5$, $0 \le y_i \le m$. $d_i$는 L 또는 R이다. $y_i = 0$이면 $d_i$는 R이고, $y_i = m$이면 $d_i$는 L이다. 답이 적어도 하나 존재함이 보장된다. 모든 데이터셋에 대한 $t$의 합은 $10^6$을 넘지 않는다. 입력의 끝은 0 두 개로 이루어진 줄이다.

각 데이터셋에 대해 $x_0$와 $v$를 공백으로 구분하여 한 줄에 출력한다.