The children in the kindergarten once decided to hang a garland for the New Year. But this turned out to be a very difficult task for them. To help, came Father Frost Pavlovitch, who now every New Year brings a garland and helps it to hang.

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

Input

The first line contains integer n (2 ≤ n ≤ 100000). Second line contains the line with n letters (all letters are: u, d or h) the last year's garland.

Output

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