0622 - 蟻

時間制限 3 秒 / メモリ制限 256 MB / 得点 11 / Writer ei1417 / x 4 / 統計 /


TLE
3sec
MLE
256MB
得点
11

問題

大きなチェス盤上に、それぞれ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≦xiW)、南北方向の位置yi(1≦yiH)、向きを表す文字di(東向きの場合「E」、南向きの場合「S」)が与えられる。ここで、チェス盤の北西角のマスを(1,1)、xが増加する方向を東、yが増加する方向を南とする。

時間制限

入力に対して、実行時間が3秒を超えてはならない。

出力

落下する順番に、蟻の番号を1行ずつ出力する。


入出力例

入力例1

3 3 3
2 1 S
1 2 E
2 2 E

出力例1

3
1
2

入力例2

5 4 3
3 1 S
2 2 E
1 3 E

出力例2

2
3
1