Đề bài

Ondra vừa được thăng chức Đại đô đốc Hải quân Cộng hòa Séc. Tuy nhiên, ngay khi anh bắt đầu nghĩ rằng mình đã có một công việc ổn định, chính phủ công bố cắt giảm ngân sách, trong đó có việc giải thể Hải quân.

Vì vậy, Ondra quyết định chứng minh cho chính phủ thấy Hải quân Séc quan trọng đến mức nào. Nhờ các gián điệp, anh biết về một trận hải chiến sắp diễn ra giữa bốn hạm đội lớn. Nếu có thể giành chiến thắng, chắc chắn anh sẽ tạo ra một màn thể hiện đủ sức thuyết phục.

Đáng tiếc, Hải quân Séc không có tàu chiến cũng chẳng có cảng biển. Nhưng nếu các gián điệp của Ondra chiếm được một số tàu, anh có thể vẫn còn cơ hội. Giá như anh biết được những con tàu nào sẽ sống sót sau trận chiến...

Một trận hải chiến diễn ra như sau. Ban đầu, tàu \(i\) nằm tại ô \((x_i,y_i)\), trong đó cả \(x_i\) và \(y_i\) đều là số chẵn. Mỗi tàu thuộc một trong bốn hạm đội: Bắc, Nam, Đông hoặc Tây. Sau đó, trận chiến diễn ra theo từng bước. Trong mỗi bước:

• Trước tiên, mọi tàu đồng thời di chuyển một ô theo hướng tương ứng với hạm đội của mình.
• Nếu lúc này có ít nhất hai tàu cùng nằm trên một ô, tất cả các tàu đó chìm và biến mất khỏi bản đồ.

Trận chiến kết thúc khi không còn vụ va chạm nào có thể xảy ra. Một tàu sống sót là tàu vẫn còn trên bản đồ sau khi trận chiến kết thúc.

Tàu di chuyển theo hướng của hạm đội, làm thay đổi tọa độ như sau:

• Bắc (N): giảm tọa độ \(y\) đi \(1\).
• Nam (S): tăng tọa độ \(y\) thêm \(1\).
• Đông (E): tăng tọa độ \(x\) thêm \(1\).
• Tây (W): giảm tọa độ \(x\) đi \(1\).

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(N\). Mỗi dòng trong \(N\) dòng tiếp theo chứa ba giá trị \(x_i\), \(y_i\) và \(d_i\), cách nhau bởi dấu cách. Hai số nguyên \(x_i\), \(y_i\) là tọa độ của tàu thứ \(i\). Ký tự \(d_i\) là một trong N, S, E, W, mô tả hướng của hạm đội chứa tàu thứ \(i\).

Không có hai tàu nào có cùng tọa độ ban đầu. Nói cách khác, với hai tàu \(i\) và \(j\) (\(i\ne j\)), ta có \(x_i\ne x_j\) hoặc \(y_i\ne y_j\).

Dữ liệu ra

Với mỗi tàu sống sót, in một dòng chứa số nguyên \(i\) (\(1\le i\le N\)), là chỉ số của tàu đó. Bạn có thể in chỉ số các tàu sống sót theo thứ tự bất kỳ.

Nếu không có tàu nào sống sót, dữ liệu ra phải rỗng.

Giới hạn

• \(2\le N\le 2\cdot 10^5\).
• \(0\le x_i,y_i\le 10^9\) với mọi \(1\le i\le N\); \(x_i\) và \(y_i\) đều là số chẵn.

Chấm điểm

• Subtask 1 (6 điểm): \(N=2\).
• Subtask 2 (12 điểm): \(N\le 100\) và \(x_i,y_i\le 100\) với mọi \(1\le i\le N\).
• Subtask 3 (8 điểm): \(N\le 100\) và \(x_i,y_i\le 10^5\) với mọi \(1\le i\le N\).
• Subtask 4 (11 điểm): \(N\le 200\).
• Subtask 5 (9 điểm): \(N\le 5\,000\).
• Subtask 6 (30 điểm): \(d_i\) là S hoặc E với mọi \(1\le i\le N\).
• Subtask 7 (24 điểm): Không có ràng buộc bổ sung.

Ví dụ

7
0 6 E
0 8 E
2 4 E
4 2 S
6 0 S
6 2 S
6 4 S

7

5
4 0 S
0 2 E
2 2 E
4 4 N
6 6 W

5
2