Петя и Вася продолжали играть в шпионов. Однако на этот раз вероятный противник в лице Васиной бабушки захватил Васю и увез на секретную дачу. В течение нескольких дней Вася ожидал спасения, когда вдруг понял, что Петя знает, где находится дача его бабушки. А это никак не укладывалось в сценарий игры в шпионов. Чтобы хоть немного спасти положение, Вася решил поставить в лесу вокруг бабушкиной дачи часовых - других своих друзей, которые должны мешать Пете его спасать. Для точности Вася взял план местности, ввел на нем систему координат, направив ось \textbf{Oy} на север, а ось \textbf{Ox} - на восток, и отметил на нем часовых. Кроме того, каждому часовому Вася выдал мощный фонарик, который освещает угол величины \textbf{90} градусов перед часовым. Так как фонарики мощные, то они светят практически на любое расстояние. Затем Вася решил, что Пете может быть слишком сложно пробираться на дачу, и разрешил часовым светить фонариком только в одном из четырех направлений - строго на север, запад, юг или восток, так чтобы биссектриса угла, освещаемого фонариком часового, совпадала с этим направлением. Теперь, чтобы оценить свои шансы быть спасенным, Вася хочет для каждого часового узнать скольких часовых, помимо него самого, освещает его фонарик. \InputFile В первой строке входного файла дано целое число \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{50000}) - число часовых в лесу. В следующих \textbf{n} строках содержатся данные о часовых. В \textbf{i}-й строке записаны два целых числа \textbf{x_i} и \textbf{y_i} (|\textbf{x_i}|, |\textbf{y_i}| ≤ \textbf{10^9}) - координаты \textbf{i}-го часового на плане Пети и направление, куда смотрит часовой - \textbf{N}, \textbf{E}, \textbf{S}, \textbf{W}, соответствующие северу, востоку, югу и западу. Никакие два часовых не находятся в одной точке. \OutputFile В выходной файл выведите \textbf{n} строк. В \textbf{i} строке должно содержаться единственное целое число - скольких часовых освещает фонарик \textbf{i}-го часового, помимо него самого. \Note Первый пример \includegraphics{https://static.e-olymp.com/content/dd/dd75476573bb6ccce8ba1de149eb6f4a5af2de63.jpg} Второй пример \includegraphics{https://static.e-olymp.com/content/dd/dd75476573bb6ccce8ba1de149eb6f4a5af2de63.jpg}