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

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