SPOJ in Gyumri

   Vasya is a conductor on a bus serving quite an unpopular route, so he is loafing most of his working hours. In order to kill time he often plays a game. He takes a piece of his ticket roll and starts looking for lucky tickets. The tickets in the roll have sequen- tial six-digit numbers. A ticket is lucky if the sum of the first three digits of its num- ber is equal to the sum of the other three. Vasya records his observations making a string of capital Latin letters, writing down “L” for a lucky ticket, and “U” for a common one. For example, for the roll of 10 tickets numbered 001001, 001002, 001003, 001004, 001005, 001006, 001007, 001008, 001009, 001010, the resulting string will be “LUUUUUUUUL”.

   Eventually, Vasya considered an inverse problem: would it be possible to come up with a ticket roll for a given string consisting of “L” and “U” characters? The answer turned out to be negative. For example, there is no roll having two consecutive lucky tickets, that is, no ticket roll exists for string “LL”.

   Your task is to write a program that will find a ticket roll corresponding to the given string of “L” and “U” characters, or report that no such roll exists. In case of several possible solutions, the correct roll is the one with the least number of the first ticket.

Limitations

   The input string contains capital letters “L” and “U” only. Its length does not exceed 1000 characters. The input string is non-empty.

Input

   The first line of the input file contains an integer n, the number of characters in the input string. The second line contains n characters. The only valid characters here are capital Latin letters “L” and “U”.

Output

   The output file should contain either a six-digit integer, the number of the first ticket in the roll corresponding to the input string, or the message “No solution” (without quotation marks) if no such roll exists.

Example