ウェーブマシンは,波のふるまいを観察するための物理実験装置である.この装置上では横波を発生させることができ,発生した波は一定の速さで進行し,装置の両端で反射する.
この問題で考える波は,波長の極めて短い 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 である.
入力は複数のデータセットからなる.データセットの個数は 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 つのゼロからなる行で表される.