Часовые

Петя и Вася продолжали играть в шпионов. Однако на этот раз вероятный противник в лице Васиной бабушки захватил Васю и увез на секретную дачу. В течение нескольких дней Вася ожидал спасения, когда вдруг понял, что Петя знает, где находится дача его бабушки. А это никак не укладывалось в сценарий игры в шпионов. Чтобы хоть немного спасти положение, Вася решил поставить в лесу вокруг бабушкиной дачи часовых - других своих друзей, которые должны мешать Пете его спасать.

Для точности Вася взял план местности, ввел на нем систему координат, направив ось 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-го часового, помимо него самого.

Примеры

Примечание

Первый пример

Второй пример