Children in a kindergarten once decided to decorate the room with a garland for the Christmas Day. But this turned out to be a difficult task for them. Santa Claus Petrovich came to help them, and now each year he brings a garland and helps to hang it.

A garland is a plane broken line consisting of N segments. The garland starts at the point (0, 0), at the socket, and must end at the point (N, 0). The number N is called the length of the garland. Each segment can be either horizontal or lie at an angle 45° to the axis OX. The length of horizontal projection of each segment equals 1. There are no vertices of the broken line with a negative y coordinate and no two successive vertices with zero y coordinates. Let us call a segment ascending (descending) if the y coordinate of its right end is greater (respectively, less) than the y coordinate of its left end. A segment with coinciding y coordinates of its left and right ends is called horizontal. We denote an ascending segment by the letter 'u', a descending segment by the letter 'd', and a horizontal segment by the letter 'h'. Then a garland is coded as a string of N symbols.

Santa Claus Petrovich has a magical book, in which all garlands of length N are listed in the form of strings. Though the book is magical, the strings are arranged in the standard way, i.e., in the ascending lexicographical order. Santa Claus Petrovich ticked off on the margin the garland he hung last year. This year he wants to hang the garland that is next in the book. Try to find this garland without the magical book.

The first line contains the integer N (2 ≤ N ≤ 100000). The second line is a string containing N letters (each of them is 'u', 'd', or 'h'). This string describes last year's garland.

Output a string describing the garland that Santa Claus Petrovich should bring this Christmas or “No solution” if such a garland does not exist.