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 sequential six-digit
numbers. A ticket is lucky if the sum of the first three digits of its number
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
|
Input
|
Output
|
|
10
LUUUUUUUUU
|
000000
|
|
10
LUUULUUUUU
|
No solution
|
|
10
LUUUUUUUUL
|
001001
|
