Новорічна гірлянда

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

Гірлянда являє собою ламану у площині, яка складається з $n$ ланок. Гірлянда починається у точці $(0,0)$ біля електророзетки і повинна завершуватись у точці $(n,0)$. Число $n$ називається довжиною гірлянди. Кожна ланка може розміщуватись або горизонтально, або під кутом 45^\circ до осі $OX$. Довжина горизонтальної проекції довільної ланки дорівнює $1$. При цьому не повинно бути вершини ламаної з від'ємною координатою $y$, а також двох послідовних вершин з нульовою координатою $y$. Висхідною (низхідною) назвемо ланку ламаної, у якої координата $y$ правого кінця більша (відповідно, менша) координати $y$ лівого кінця. Ланку, у якої координати $y$ кінців співпадають, назвемо горизонтальною. Позначимо висхідну ланку літерою $u$, низхідну — літерою $d$, а горизонтальну — літерою $h$. Тоді гірлянда кодується рядком з $n$ символів. У Діда Мороза Павловича є чарівна книга, у якій перераховані усі гірлянди довжини $n$ у вигляді рядків. Хоча книга й чарівна, рядки у ній розміщуються у звичайному лексикографічному порядку, за зростанням. Дід Мороз Павлович відмітив на полях галочкою гірлянду, яку повісив минулого разу. У цей Новий рік він хоче повісити наступну у книзі гірлянду. Знайдіть цю гірлянду без використання чарівної книги.