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 1000\)) 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, và từ đó về sau vẫn đứng yên, 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.

Farmer John không vui khi thấy bò ngừng gặm cỏ và muốn biết phải trách ai. Nếu bò \(b\) dừng trong một ô mà bò \(a\) đã ăn cỏ trước đó, ta nói bò \(a\) đã chặn bò \(b\). Hơn nữa, nếu bò \(a\) chặn bò \(b\) và bò \(b\) chặn bò \(c\), ta cũng nói bò \(a\) đã chặn bò \(c\); quan hệ "chặn" có tính bắc cầu. Mức trách nhiệm của mỗi con bò bằng số bò mà nó đã chặn. Hãy tính mức trách nhiệm của từng con bò.

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à mức trách nhiệm của con bò thứ \(i\) trong dữ liệu vào.

Phân nhóm

• Trong các test 2-5, mọi tọa độ không vượt quá \(2000\).
• 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 1
E 9 2

0
0
1
2
1
0

Nguồn

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

Tác giả: Brian Dean.