Farmer John vừa mở rộng trang trại, nên từ góc nhìn của đàn bò, trang trại giờ gần như vô hạn! Những chú bò xem khu vực chăn thả là một lưới ô vuông hai chiều vô hạn, mỗi ô đầy cỏ ngon. Mỗi con trong số \(N\) con bò của Farmer John (\(1\le N\le 50\)) bắt đầu ở một ô khác nhau; một số con quay mặt về phía bắc, số còn lại quay mặt về phía đông.

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

• Dừng lại nếu cỏ trong ô hiện tại đã bị một con bò khác ăn.
• Nếu không, ăn hết cỏ trong ô hiện tại rồi đi thẳng một ô theo hướng đang quay mặt.

Theo thời gian, mỗi con bò để lại phía sau một "vệt" gồm các ô trống không còn cỏ. Nếu hai con bò đi vào cùng một ô còn cỏ trong cùng một lượt, chúng cùng ở trong ô đó và tiếp tục đi theo hướng tương ứng vào giờ tiếp theo.

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

Dữ liệu vào

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

Để làm rõ hướng và tọa độ: nếu một con bò ở ô \((x,y)\) và đi về phía bắc, nó đến ô \((x,y+1)\). Nếu đi về phía đông, nó đến ô \((x+1,y)\).

Dữ liệu ra

In \(N\) dòng. Dòng thứ \(i\) là số ô cỏ mà con bò thứ \(i\) trong dữ liệu vào ăn. Nếu con bò ăn vô hạn cỏ, in Infinity.

Phân nhóm

• Trong các test 2-5, mọi tọa độ không vượt quá \(100\).
• Trong các test 6-10, không có ràng buộc bổ sung.

Ví dụ

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

5
3
Infinity
Infinity
2
5

Nguồn

USACO 2020 December Contest, Bronze - Stuck in a Rut: https://usaco.org/index.php?page=viewproblem2&cpid=1061

Tác giả: Brian Dean.