Нещодавно Фермер Джон збільшив розмір своєї ферми, тепер з погляду корів, вона нескінченна за розміром. Корови представляють пасовище ферми як нескінченну 2D гратку квадратних комірок, кожна з яких заповнена смачною травою. (Думайте про кожну комірку як про клітку на шахівниці). Кожна з \(N\) корів (\(1\le N\le 1000\)) ФД починає пастися в різній комірці. Деякі починають, дивлячись на північ, а деякі – на схід.

Кожну годину корова або

• Зупиняється, якщо трава в поточній комірці вже з'їдена іншою коровою.
• З'їдає всю траву в поточній комірці і переміщається на одну комірку вперед у своєму вихідному напрямку.

Через деякий час кожна корова залишить за собою колію порожніх комірок.

Якщо дві корови потраплять одночасно на одну і ту ж комірку з травою, вони випасуть траву разом і продовжать рух у своїх напрямках наступної години.

ФД не любить, коли корова припиняє пастись, і він хоче дізнатися, хто винен у зупинці корови. Якщо корова \(b\) зупинилася в комірці, яку випасла корова \(a\), тоді він вважає, що корова \(a\) зупинила корову \(b\). Більше того, якщо корова \(a\) зупинила корову \(b\), а корова \(b\) зупинила корову \(c\), він вважає, що корова \(a\) також зупинила корову \(c\) (тобто ставлення "зупинила" транзитивне). Кожна корова "винна" у кількості корів, які вона зупинила. Для кожної корови обчисліть кількість зупинених нею корів.

Формат вхідних даних

Перший рядок містить ціле число \(N\). Кожен із наступних \(N\) рядків описує стартову позицію корови у термінах: символ (N або E, орієнтація на північ або на схід) та два невід'ємних цілих числа \(x\) і \(y\) (\(0\le x\le 10^9\), \(0\le y\le 10^9\)) - координати комірки. Всі \(x\)-координати різні. Всі \(y\)-координати різні.

Щоб було зрозуміліше щодо напрямів та координат: якщо корова в комірці \((x,y)\) і рухається на північ, то вона потрапить у комірку \((x,y+1)\), а якщо на схід - то в комірку \((x+1, y)\).

Формат вихідних даних

Виведіть \(N\) рядків. Рядок \(i\) має описувати кількість корів, які зупинила \(i\)-а корова.

Приклад вхідних даних

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

У цьому прикладі корова 3 зупинить корову 2, корова 4 зупинить корову 5, корова 5 зупинить корову 6. За транзитивністю корова 4 зупинить корову 6.

Оцінювання:

• У тестах 2-5 усі координати не більше \(2000\).
• У тестах 6-10 немає додаткових обмежень.