Вартові
Петя і Вася продовжують грати у шпигунів. Проте на цей раз ймовірний супротивник в особі Васиної бабусі захопив Васю і повіз на секретну дачу. Протягом декількох днів Вася очікував визволення, коли раптом зрозумів, що Петя знає, де знаходиться дача його бабусі. А це ніякак не вкладалось у сценарій гри у шпигунів. Щоб хоч трішки врятувати положення, Вася вирішив поставити у лесі навколо бабусиної дачі вартових - інших своїх друзів, які повинні заважати Петі його рятувати.
Для точності Вася узяв план місевості, увів на ньому систему координат, направив вісь Oy на північ, а вісь Ox - на схід, і відмітив на ньому вартових. Крім того, кожному вартовому Вася видав потужний ліктарик, який освітлює кут величиною 90 градусів перед вартовим. Так як ліхтарики потужні, то вони світять практично на довільну відстань. Потім Вася вирішив, що Петі може бути занадто складно пробиратись на дачу, і дозволив вартовим світити ліхтариком лише у одному з чотирьох напрямків - строго на північ, захід, південь або схід, так щоб бісектриса кута, який освітлюється ліхтариком вартового, співпадала з цим напрямком.
Тепер, щоб оцінити свої шанси бути врятованим, Вася хоче для кожного вартового взнати скільких вартових, крім нього самого, освітлює його ліхтарик.
Вхідні дані
У першому рядку вхідного файлу задано ціле число n (1 ≤ n ≤ 50000) - кількість вартових у лісі. У наступних n рядках містяться дані про вартових. У i-му рядку записано два цілих числа x_i та y_i (|x_i|, |y_i| ≤ 10^9) - координати i-го вартового на плані Петі та напрямок, куди дивиться вартовий - N, E, S, W, які відповідають півночі, сходу, півдню та заходу. Ніякі два вартових не знаходяться в одній точці.
Вихідні дані
У вихідний файл виведіть n рядків. У i-му рядку повинно міститись єдине ціле число - скільки вартових освітлює ліхтарик i-го вартового, крім нього самого.
Пояснення до прикладів
Перший приклад
Другий приклад