ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Ural SU contest. Petrozavodsk training camp. Winter 2006

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

C. Новогодняя гирлянда

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Дети в детском саду как-то раз решили повесить к Новому году новогоднюю гирлянду. Но это оказалось для них очень трудной задачей. На помощь пришёл Дед Мороз Петрович, который теперь каждый Новый год приносит с собой гирлянду и помогает её повесить.
Гирлянда представляет собой ломаную в плоскости, состоящую из N звеньев. Гирлянда начинается в точке (0, 0), возле электророзетки, и должна заканчиваться в точке (N, 0). Число N назывется длиной гирлянды. Каждое звено может располагаться либо горизонтально, либо под углом 45° к оси OX. Длина горизонтальной проекции любого звена равна 1. При этом не должно быть вершины ломаной с отрицательной координатой y, а также двух последовательных вершин с нулевой координатой y. Поднимающимся (опускающимся) назовём звено ломаной, у которого координата y правого конца больше (соответственно, меньше) координаты y левого конца. Звено, у которого координаты y концов совпадают, назовём горизонтальным. Обозначим поднимающееся звено буквой 'u', опускающееся — буквой 'd', а горизонтальное — буквой 'h'. Тогда гирлянда кодируется строкой из N символов.
У Деда Мороза Петровича есть волшебная книга, в которой перечислены все гирлянды длины N в виде строк. Хотя книга и волшебная, но строки в ней располагаются в обычном лексикографическом порядке, по возрастанию. Дед Мороз Петрович отметил на полях книги галочкой гирлянду, которую повесил в прошлый раз. В этот Новый год он хочет повесить следующую в книге гирлянду. Попробуйте без волшебной книги найти, какую.

Исходные данные

В первой строке — целое число N (2 ≤ N ≤ 100000). Во второй строке — строчка из N букв (все буквы: 'u', 'd', либо 'h') — прошлогодняя гирлянда.

Результат

Выведите в виде строки гирлянду, которую Дед Мороз Петрович должен прихватить с собой в этот Новый год, либо «No solution», если такой гирлянды не существует.

Пример

исходные данныерезультат
6
uhduhd
uhhdud
Автор задачи: Александр Торопов, особая благодарность Дмитрию Иванкову
Источник задачи: Ural SU Contest. Petrozavodsk Winter Session, January 2006
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1461. Новогодняя гирлянда