Дети в детском саду как-то раз решили повесть к Новому году гирлянду. Но это оказалось для них очень трудной задачей. На помощь пришёл Дед Мороз Павлович, который теперь каждый Новый год приносит с собой гирлянду и помогает её повесить.

Гирлянда представляет собой ломаную в плоскости, состоящую из 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, если такой гирлянды не существует.