• Лавирующий катер
  BOAT

Описание
Современное оружие постоянно совершенствуется и все более компьютеризируется. Эта задача позволяет окунуться в мир борьбы с роботами

Задано поле размером 40×40 клеток. Клетки пронумерованы справа налево и снизу вверх. Таким образом, нижняя левая клетка имеет координаты (0,0), а правая верхняя - координаты (39,39). В левом нижнем углу находится катер, желающий попасть в правый верхний угол. Катер может двигаться только по горизонтали или по вертикали, но не по диагонали. Катер все время двигается с постоянной скоростью 1 клетка в секунду, управляется компьютером. 

Задача
К сожалению, компьютер катера достаточно слаб и не в силах самостоятельно рассчитать грамотную программу движения. Именно Вы должны помочь ему в этом

Программа для катера представляет собой последовательность упорядоченных троек (W, X, Y), где X - номер столбца, считая от нуля справа, Y - номер строки, считая от нуля снизу, W - один из символов N, E, W, S, означающий продолжение движения на север (вверх), восток (вправо), запад (влево) или юг (вниз). В последней команде обязательно должно выполняться X=Y=39

Работает катер так. Он считывает первую команду, и движется в указанном направлении, пока не достигнет указанной точки (X, Y). Далее он считывает очередную команду, изменяет направление движения на указанное в ней и движется, пока не достигнет новой цели (X, Y). Если, повинуясь командам, катер выходит за пределы поля, то он теряется в глубоком космосе. Катер очень мал по размерам, и если с начала его движения прошло целое количество секунд, то катер находится точно в центре клетки

Все было бы слишком просто, если бы на поле больше ничего не было. Но на поле размещены стационарные заграждения вражеских роботов, известных в народе как "радары". Каждый радар определяется клеткой размещения, радиусом действия и начальным положением луча. Действует радар так. Его луч непрерывно движется с некоторой угловой скоростью по квадрату поражения. Если луч пересекает точку, в которой находится катер, то последний немедленно погибает. Катер погибает также и в случае непосредственного наезда на радар. Определим теперь квадрат поражения

От точки расположения радара отложим вправо, влево, вверх и вниз заданный радиус действия. Построим на поле минимальный квадрат из клеток, содержащий полученные четыре точки - это и будет квадрат поражения. Начальное положение луча задается координатами клетки его конца (начало луча - в центре квадрата поражения). Далее каждую секунду луч перемещается на одну клетку по периметру квадрата поражения по часовой стрелке. Луч очень тонкий, и если с начала движения катера прошло целое количество секунд, то конец луча находится точно в центре клетки. Гарантируется, что все квадраты поражения не выходят за границы поля. В одной клетке могут располагаться несколько радаров. Далее на рисунке - пример радара радиуса действия 2

По периметру квадрата поражения расставлены цифры по порядку их "посещения" концом луча. Ваша задача - написать программу, которая по заданному расположению радаров на поле выдаст некоторую программу, приводящую катер из клетки (0,0) в клетку (39,39) целым и невредимым. Если это невозможно (слишком много радаров), то программа должна выдать в выходной файл единственную строчку "No solution", в противном случае - программу для катера

Каждая команда для катера должна быть записана в одной отдельной строке, элементы команды (т.е, значения W, X, Y) записаны через один или несколько пробелов. Пустых строк между командами быть не должно


Формат входных данных
В первой строке указано число радаров R (1<=R<=50). В следующих R строках указаны конфигурации радаров, по одной в каждой строке. Конфигурация радара указана в виде чисел X, Y, I, J, разделенных одним или несколькими пробелами. X, Y - координаты расположения радара, I, J - координаты клетки, в центре которой находится конец луча в начальный момент времени. Все координаты - целые числа от 0 до 39.

Формат выходных данных
Единственная строка с текстом "No solution", либо программа движения катера в указанном выше формате


Например:

BOAT.DAT
6
3 3 1 1
7 7 5 5
19 19 13 13
33 33 39 39
19 19 19 0
6 33 6 39

BOAT.SOL
N 0 20
E 30 20
N 30 39
E 39 39


Замечание
Катер представляет собой непрерывно и равномерно движущуюся точку, луч - непрерывно движущийся отрезок. Луч движется так, что его конец перемещается по периметру квадрата поражения с постоянной по модулю скоростью. Неверно рассматривать луч как набор клеток, или катер - как движущееся тело размером с клетку