Застрягти в колії (Срібло)#10369

Застрягти в колії (Срібло)

1 секунда

128 мегабайтів

Складна

Фермер Джон нещодавно розширив свою ферму, і тепер вона здається його коровам безмежно великою! Корови уявляють пасовища на фермі як нескінченну двовимірну сітку квадратних "клітинок", кожна з яких вкрита смачною травою (уявіть кожну клітинку як квадрат на нескінченній шаховій дошці). Кожна з $n$ корів фермера Джона починає з різних клітинок; деякі рухаються на північ, а інші — на схід.

Щогодини кожна корова або:

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

Таким чином, з часом кожна корова залишає за собою "колію" порожніх клітинок.

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

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

Вхідні дані

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

Якщо корова знаходиться в точці $(x, y)$ і рухається на північ, вона опиниться в точці $(x, y + 1)$ (x, y + 1). Якщо вона рухається на схід, вона опиниться в точці $(x + 1, y)$ (x + 1, y).

Вихідні дані

Виведіть $n$ рядків. Рядок номер $i$ повинен містити значення вини $i$ -ої корови з вхідних даних.

Приклади

Приклад 1

Примітка

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