Farmer John gần đây mở rộng trang trại, nên trong mắt bò giờ nó gần như vô hạn! Bò coi đồng cỏ là lưới hai chiều vô hạn gồm các ô vuông đầy cỏ ngon (như ô trên bàn cờ vô hạn). Mỗi con trong $N$ con bò ($1\le N\le 50$) bắt đầu ở một ô khác nhau; có con hướng bắc, có con hướng đông.

Mỗi giờ, mỗi con bò thực hiện một trong hai việc:

• Dừng nếu cỏ ở ô hiện tại đã bị một con bò khác ăn.
• Ăn hết cỏ ở ô hiện tại và đi tới một ô theo hướng đang nhìn.

Theo thời gian, mỗi con để lại một «vệt» trơ trụi gồm các ô rỗng phía sau.

Nếu hai con vào cùng một ô có cỏ trong cùng một lần di chuyển, chúng chia sẻ ô đó và tiếp tục theo hướng riêng trong giờ tiếp theo.

Hãy xác định lượng cỏ mỗi con ăn. Một số con không bao giờ dừng và ăn lượng cỏ vô hạn.

Dữ liệu vào

Dòng đầu chứa $N$. Mỗi dòng trong $N$ dòng sau mô tả vị trí đầu của một con bằng ký tự N (bắc) hoặc E (đông) và hai số nguyên không âm $x$, $y$ ($0\le x\le 10^9$, $0\le y\le 10^9$), tọa độ ô. Mọi tọa độ $x$ khác nhau, và mọi tọa độ $y$ cũng khác nhau.

Để làm rõ hướng và tọa độ, từ $(x,y)$ đi bắc tới $(x,y+1)$, còn đi đông tới $(x+1, y)$.

Dữ liệu ra

In $N$ dòng. Dòng $i$ cho biết số ô cỏ mà con bò thứ $i$ trong đầu vào ăn. Nếu lượng cỏ vô hạn, in Infinity cho con đó.

Ví dụ

Dữ liệu vào 1

6
E 3 5
N 5 3
E 4 6
E 10 4
N 11 2
N 8 1

Dữ liệu ra 1

5
3
Infinity
Infinity
2
5

Nhiệm vụ con

• Trong các bộ kiểm thử từ $2$ đến $5$, mọi tọa độ không quá $100$.
• Trong các bộ kiểm thử từ $6$ đến $10$, không có ràng buộc thêm.

Tác giả bài toán: Brian Dean