蟻

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

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

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

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

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

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

Input

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

W H N
x1 y1 d1
x2 y2 d2
:
xN yN dN

１行目にチェス盤の東西方向のマスの数 W と南北方向のマスの数 H (2 ≤ W, H ≤ 10⁹) と蟻の数 N (1 ≤ N ≤ 200000) が与えられる。続く N 行に i 番目の蟻の東西方向の位置 x_i (1 ≤ x_i ≤ W)、南北方向の位置 y_i (1 ≤ y_i ≤ H)、向きを表す文字 d_i（東向きの場合「E」、南向きの場合「S」）が与えられる。ここで、チェス盤の北西角のマスを (1,1)、x が増加する方向を東、y が増加する方向を南とする。

Output

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

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