Вартові#2786
Петя і Вася знову грають у шпигунів. Цього разу бабуся Васі, яка виступає у ролі противника, схопила Васю і відвезла його на секретну дачу. Провівши кілька днів у очікуванні рятунку, Вася зрозумів, що Петя знає місцезнаходження бабусиної дачі, що не відповідало їхній «шпигунській» грі. Щоб зробити гру складнішою, Вася вирішив розставити в лісі навколо дачі друзів-стражників, аби не дати Петі його врятувати.
Вася скористався картою місцевості, ввів систему координат із віссю Oy, спрямованою на північ, і віссю Ox, спрямованою на схід, та позначив місця розташування стражників. Кожен стражник був озброєний потужним ліхтарем, що освітлює кут у 90 градусів перед ним. Ці ліхтарі настільки сильні, що світять на будь-яку відстань. Проте, щоб дати Петі шанс на порятунок, Вася дозволив стражникам спрямовувати ліхтар тільки в один із чотирьох напрямків: строго на північ, захід, південь або схід. Бісектриса кута ліхтаря спрямована точно у вказаний напрямок.
Щоб оцінити свої шанси на порятунок, Вася хоче дізнатися, скільки інших стражників потрапляють у промінь ліхтаря кожного стражника.
У першому рядку записано одне ціле число (1 \leq n \leq 50000) — кількість стражників в лісі. Далі у наступних рядках записано інформацію про кожного стражника. -й рядок містить два цілих числа x_i і y_i (|x_i|, |y_i| \leq 10^9) — координати -го стражника на карті Петі, а також букву, яка вказує напрямок, куди він дивиться: N, E, S або W (північ, схід, південь або захід відповідно). Жодні два стражники не мають однакових координат.
Виведіть рядків. У -му рядку виведіть одне ціле число — скільки стражників освітлює ліхтар -го стражника, не враховуючи самого себе.
Приклад 1
Пояснення до прикладів
Перший приклад
Другий приклад