Фирма "Макрохард" изобрела новое устройство с целью облегчить труд людей, кому по долгу службы приходится чертить много чертежей, а также школьников, изучающих черчение. Это устройство представляет собой крошечного робота, который умеет ползать по клетчатому листу бумаги. При этом в начале он обязательно должен быть расположен на пересечении линий сетки.

Этот робот умеет выполнять программу, которая может состоять из команд E,W,N,S — переместиться по листу в соседнюю вершину сетки вправо, влево, вперед, назад соответственно. Перемещаясь в соседний узел сетки, робот оставляет за собой ровную линию. При этом по правилам техники безопасности ему категорически запрещается проводить дважды одну и ту же линию, так как при попытке провести линию второй раз, он очень сильно пачкается в своих же собственных чернилах (они очень долго сохнут), и выходит из строя.

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

В первом случае мы оба раза проезжаем через вершину "прямо" (будем называть это самопересечением маршрута), а во втором случае — оба раза "поворачиваем" (это будем называть самокасанием).

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

Вам дается программа для робота. Требуется изменить ее так, чтобы узор, получающийся в конце ее работы, был таким же, но при этом при работе робота не возникало самопересечений маршрута.

Учёные любят присваивать идентификаторы всему живому. Поэтому они обозначают динозавров I эпохи кодом `a'. Динозавры II эпохи, как произошедшие от динозавров I эпохи, именуются кодом `aba'. Ящеры III эпохи – `abacaba', и вообще если \(C\)(\(n\)) – код динозавров эпохи \(n\), то \(C\)(\(n\)+1)=\(C\)(\(n\))+\(S\)(\(n\)+1)+\(C\)(\(n\)) , где \(S\)(\(n\)+1) – символ очередной (\(n\)+1-ой) эпохи. Символ первой эпохи – `a' , символ второй эпохи – `b', затем `c', `d', …, `x', `y', `z'. После букв учёные почему-то перешли на цифры, и обозначили эпохи с XXVII по XXXVI соответственно `0', `1', …, `9' .

После XXXVI эпохи динозавры вымерли, и уже утверждённое название XXXVII эпохи (`α') отдали астрономам для нового кратера на Марсе.

Астрономы (в знак благодарности) нашли какую-то отдалённую звезду с огромной статуей динозавра, похожего на земные аналоги. Экспедиция, посетившая указанную звезду, нашла под статуей надпись, очевидно, с кодом этого динозавра. Впрочем, часть надписи стёрлась. Теперь учёные хотят максимально завысить древность находки. Для этого нужно определить, в коде динозавров какой эпохи – самой древней из подходящих – встречается данный образец (как подстрока). Такую задачу не по силам решить даже астрономам.