acm International Collegiate Programming Contest

Links

A B C D E F G H I

Problem H

物理実験

ウェーブマシンは,波のふるまいを観察するための物理実験装置である.この装置上では横波を発生させることができ,発生した波は一定の速さで進行し,装置の両端で反射する.

この問題で考える波は,波長の極めて短い 1 周期の波のみであり,その位置は点とみなせるものとする.いま,任意の実数 x ≥ 0 について,ウェーブマシンの左端から右に x 離れた位置の座標を x と定義する.また,ウェーブマシンの右端の座標を m としよう.ウェーブマシンの左端で波を発生させたとき,はじめ,波はある速さ v で右方向に進行する.波が座標 m に到達したとき,波は反射し,同じ速さのまま進行方向は左向きとなる.同様に,波が座標 0 に到達したとき,波の進行方向は右向きとなる.また,ウェーブマシンの両端以外の場所で波が反射することはない.したがって,一度発生した波は,長さ m のウェーブマシン上を,一定の速さ v で往復し続けることになる.

あなたは,物理の実験で,ウェーブマシン上に波を発生させ,その座標と進行方向を記録し続けることになった.はじめ,あなたはウェーブマシンの左端で波を発生させ,しばらく待機した.そして,あなたが観測を開始した時刻 0 において,この波はある座標 x0 に位置し,そのときの波の進行方向は右向きであった.その後あなたは,この波の座標と進行方向を,1 単位時間ごとに計 t 回記録した.

記録も終わり,さあ,あとは実験レポートを書くだけだ!とあなたは意気込んでいるところかもしれないが,ちょっと待ってほしい.うっかり者のあなたは,時刻 0 での波の位置の座標 x0 および速さ v を記録し忘れてしまっていた.加えて,t 個の記録をバラバラに並べ替えてしまい,どの記録がどの時刻のものかわからなくなってしまった.なんとしても再実験を避けたいあなたは,残された記録に矛盾しない x0 および v の値を用いて,実験レポートを書くことにした.

入力として,ウェーブマシンの長さ m および t 個の記録が与えられる.各記録は波の座標 yi および進行方向 di からなり,これは時刻 1, ... , t のうちのいずれかのものである.なお,座標 0 における波の進行方向は常に右向き,座標 m における波の進行方向は常に左向きとする.あなたの目的は,以下のすべての条件を満たす x0 および v の値を 1 組求めることである.なお,複数の解が存在するならば,そのうちどれを出力してもよい.

  • 時刻 0 における波の進行方向は右向きである.
  • 時刻 0 における波の位置の座標 x0 は,0 以上 m-1 以下の整数である.すなわち,座標 x0 はウェーブマシンの右端ではない.
  • 波の速さ v は,1 以上 2m 以下の整数である.
  • (1, ..., t) の順列 (p1, ..., pt) が存在し,任意の整数 j (1 ≤ j ≤ t) について,時刻 pj における波の座標は yj,進行方向は dj である.

Input

入力は複数のデータセットからなる.データセットの個数は 50 を超えない.各データセットは次の形式で表される.

m t y1 d1  ⋮ yt dt

m はウェーブマシンの長さを表す整数であり,1 ≤ m ≤ 109 を満たす.t は記録の数を表す整数であり,2 ≤ t ≤ 105 を満たす.yi はある時刻における波の位置の座標を表す整数であり,0 ≤ y ≤ m を満たす.di は L または R であり,L であればその時刻における波の進行方向が左向きであることを,R であれば右向きであることを表す.ここで,yi = 0 であれば di は R であり,yi = m であれば di は L であることが保証される.

与えられる入力に対して,答えが少なくとも 1 つ存在することが保証される.

また,すべてのデータセットに対する t の合計は 106 を超えない.

入力の終わりは 2 つのゼロからなる行で表される.

Output

条件を満たす x0 および v の値を,空白区切りで 1 行に出力せよ.条件を満たす解が複数存在するならば,そのうちどれを出力してもよい.

Sample Input

10 6
8 R
8 L
6 L
0 R
6 R
2 L
1 5
1 L
1 L
0 R
0 R
1 L
0 0

Sample Output

4 14
0 1
(End of Problem H) A B C D E F G H I