АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

1331. Bus Conductor

Ограничение времени: 0.2 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

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

 

 


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Чемпионат ACM / Рыбинск-2014 /
1330. F - Sages 1331. 1332. H - Cryptography 1333. I - Belt Drive 1334. J - Dominoes
 
время генерации 0.078 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.