Ant

Time Limit : 3 sec, Memory Limit : 262144 KB

大きなチェス盤上に、それぞれ1から N までの番号が割り振られた N 匹の蟻がいます。図のように、チェス盤は H×W のマスからなる長方形で、北西角を白として、白マスと黒マスが交互に並んでいます。



最初、どの蟻もチェス盤のマスの中にいて、東または南を向いています。1つのマスの中に2匹以上の蟻がいることはありません。

今、蟻たちが一斉に動き出します。すべての蟻は 1 単位時間に向いている方向のマスに1つ移動します。ただし、移動先がチェス盤の外の場合、落下してチェス盤から姿を消します。

チェス盤上で2匹の蟻が同じマスに入ると、それらの蟻は以下のような行動をとります:

  • そのマスの色が白ならば、東方向に進んでいた蟻は南方向へ、南方向に進んでいた蟻は東方向へ向きを変える。
  • そのマスの色が黒ならば、それぞれの蟻は進む方向を維持する。

チェス盤の大きさと蟻の情報が与えられたとき、落下する順番に蟻の番号を報告するプログラムを作成せよ。ただし、同じ時刻に複数の蟻が落下する場合は、番号がより小さい方を先に報告する。

Input

入力は以下の形式で与えられる。

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 が増加する方向を南とする。

Output

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

Sample Input 1

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

Sample Output 1

3
1
2

Sample Input 2

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

Sample Output 2

2
3
1

Source: PC Koshien 2016 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2016-11-12
http://web-ext.u-aizu.ac.jp/pc-concours/