問題
大きなチェス盤上に、それぞれ１からNまでの番号が割り振られたN匹の蟻がいます。図のように、チェス盤はH×Wのマスからなる長方形で、北西角を白として、白マスと黒マスが交互に並んでいます。
最初、どの蟻もチェス盤のマスの中にいて、東または南を向いています。１つのマスの中に２匹以上の蟻がいることはありません。
今、蟻たちが一斉に動き出します。すべての蟻は1単位時間に向いている方向のマスに１つ移動します。ただし、移動先がチェス盤の外の場合、落下してチェス盤から姿を消します。
チェス盤上で２匹の 蟻が同じマスに入ると、それらの蟻は以下のような行動をとります：
- そのマスの色が白ならば、東方向に進んでいた蟻は南方向へ、南方向に進んでいた蟻は東方向へ向きを変える。
- そのマスの色が黒ならば、それぞれの蟻は進む方向を維持する。
課題
チェス盤の大きさと蟻の情報が与えられたとき、落下する順番に蟻の番号を報告するプログラムを作成せよ。ただし、同じ時刻に複数の蟻が落下する場合は、番号がより小さい方を先に報告する。
入力
W H N x1 y1 d1 x2 y2 d2 . . . xN yN dN
１行目にチェス盤の東西方向のマスの数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
出力例1
3 1 2
入力例2
5 4 3 3 1 S 2 2 E 1 3 E
出力例2
2 3 1