Застрягти в колії (Срібло)
Фермер Джон нещодавно розширив свою ферму, і тепер вона здається його коровам безмежно великою! Корови уявляють пасовища на фермі як нескінченну двовимірну сітку квадратних "клітинок", кожна з яких вкрита смачною травою (уявіть кожну клітинку як квадрат на нескінченній шаховій дошці). Кожна з n корів фермера Джона починає з різних клітинок; деякі рухаються на північ, а інші — на схід.
Щогодини кожна корова або:
Зупиняється (і залишається нерухомою), якщо траву в її поточній клітинці вже з'їла інша корова.
З'їдає всю траву в своїй поточній клітинці і переміщається на одну клітинку вперед у напрямку свого руху.
Таким чином, з часом кожна корова залишає за собою "колію" порожніх клітинок.
Якщо дві корови одночасно заходять на одну і ту ж клітинку з травою, вони ділять її і продовжують рух у своїх напрямках у наступному ході.
Фермер Джон засмучений, коли бачить, що корови перестають пастися, і хоче знати, кого звинуватити в тому, що його корови зупинилися. Якщо корова b зупинилася в клітинці, яку спочатку з'їла корова a, то вважається, що корова a зупинила корову b. Більше того, якщо корова a зупинила корову b, а корова b зупинила корову c, то вважається, що корова a також зупинила корову c (тобто відношення "зупинити" є транзитивним). Кожну корову звинувачують відповідно до кількості зупинених нею корів. Обчисліть кількість звинувачень, покладених на кожну корову, тобто кількість корів, яких вона зупинила.
Вхідні дані
Перший рядок містить число n (1 ≤ n ≤ 1000). Кожен з наступних n рядків описує початкове місцезнаходження корови у вигляді символу, який є або N (рух на північ), або E (рух на схід), і два невід'ємних цілих числа x і y (0 ≤ x ≤ 10^9, 0 ≤ y ≤ 10^9), що вказують координати клітинки. Всі x-координати відрізняються одна від одної, як і y-координати.
Якщо корова знаходиться в точці (x, y) і рухається на північ, вона опиниться в точці (x, y + 1). Якщо вона рухається на схід, вона опиниться в точці (x + 1, y).
Вихідні дані
Виведіть n рядків. Рядок номер i повинен містити значення вини i-ої корови з вхідних даних.
Приклад
У цьому прикладі корова 3 зупиняє корову 2, корова 4 зупиняє корову 5, а корова 5 зупиняє корову 6. За транзитивністю корова 4 також зупиняє корову 6.