Діти у дитячому садку одного разу вирішили повісити на Новий рік гірлянду. Але це виявилось для них дуже важкою задачею. На допомогу прийшов Дід Мороз Павлович, який тепер кожного Нового року приносить з собою гірлянду і допомагає її повісити.

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