New Year's Garland
Children at the kindergarten once decided to hang a garland for New Year. However, they found it quite challenging. Father Frost Pavlovich came to their aid, and now every New Year, he brings a garland and helps them hang it.
The garland is a polyline on a plane made up of n segments. It begins at the point (0, 0) near the power outlet and must end at the point (n, 0). The number n represents the length of the garland. Each segment can be positioned either horizontally or at a 45° angle to the OX axis. The horizontal projection of any segment has a length of 1. No vertex of the polyline should have a negative y coordinate, and there should not be two consecutive vertices with a zero y coordinate. A segment is termed ascending if the y coordinate of its right end is greater than that of its left end, and descending if the opposite is true. A segment with equal y coordinates at both ends is called horizontal. We represent an ascending segment with the letter u, a descending one with the letter d, and a horizontal one with the letter h. Thus, the garland is encoded as a string of n characters. Father Frost Pavlovich possesses a magical book that lists all garlands of length n as strings. Although the book is magical, the strings are organized in regular lexicographical order, ascending. Father Frost Pavlovich marked the garland he hung last time with a tick in the margins. This New Year, he wants to hang the next garland in the book. Determine this garland without using the magical book.
Input
The first line contains an integer n (2 ≤ n ≤ 100000). The second line contains a string of n letters (each letter is either u, d, or h) representing last year's garland.
Output
Print the garland that Father Frost Pavlovich should hang this New Year as a string, or No solution if such a garland does not exist.