大きなチェス盤上に、それぞれ1から N までの番号が割り振られた N 匹の蟻がいます。図のように、チェス盤は H×W のマスからなる長方形で、北西角を白として、白マスと黒マスが交互に並んでいます。
最初、どの蟻もチェス盤のマスの中にいて、東または南を向いています。1つのマスの中に2匹以上の蟻がいることはありません。
今、蟻たちが一斉に動き出します。すべての蟻は 1 単位時間に向いている方向のマスに1つ移動します。ただし、移動先がチェス盤の外の場合、落下してチェス盤から姿を消します。
チェス盤上で2匹の蟻が同じマスに入ると、それらの蟻は以下のような行動をとります:
チェス盤の大きさと蟻の情報が与えられたとき、落下する順番に蟻の番号を報告するプログラムを作成せよ。ただし、同じ時刻に複数の蟻が落下する場合は、番号がより小さい方を先に報告する。
入力は以下の形式で与えられる。
W H N x1 y1 d1 x2 y2 d2 : xN yN dN
1行目にチェス盤の東西方向のマスの数 W と南北方向のマスの数 H (2 ≤ W, H ≤ 109) と蟻の数 N (1 ≤ N ≤ 200000) が与えられる。続く N 行に i 番目の蟻の東西方向の位置 xi (1 ≤ xi ≤ W)、南北方向の位置 yi (1 ≤ yi ≤ H)、向きを表す文字 di(東向きの場合「E」、南向きの場合「S」)が与えられる。ここで、チェス盤の北西角のマスを (1,1)、x が増加する方向を東、y が増加する方向を南とする。
落下する順番に、蟻の番号を1行ずつ出力する。
3 3 3 2 1 S 1 2 E 2 2 E
3 1 2
5 4 3 3 1 S 2 2 E 1 3 E
2 3 1