ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural SU contest. Petrozavodsk training camp. Winter 2006

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. Christmas Garland

Time limit: 1.0 second
Memory limit: 64 MB
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.


Problem Author: Alexander Toropov, special thanks to Dmitry Ivankov
Problem Source: Ural SU Contest. Petrozavodsk Winter Session, January 2006
To submit the solution for this problem go to the Problem set: 1461. Christmas Garland