Играть в Basic
Однажды солнечным днем Дик Т. Мустанг нашел в шкафу старый персональный компьютер. Он принес его в свою комнату и с ностальгией включил, увидев на экране сообщение:
ГОТОВ?
Да. BASIC.
BASIC — это язык программирования, созданный для начинающих, который был широко популярен с 1980-х по 1990-е годы. Существовало множество диалектов BASIC, некоторые из которых поддерживали оператор PLAY. Этот оператор воспроизводит музыку, когда вызывается со строкой музыкальной партитуры, написанной на языке Music Macro Language (MML). Дик обнаружил, что его компьютер поддерживает этот оператор и принимает следующие команды в MML:
Ноты: Cn, C+n, C-n, Dn, D+n, D-n, En,...,... (n = 1,2,4,8,16,32,64,128 + точки)
Каждая команда ноты состоит из музыкальной ноты и указателя длительности.
Музыкальная нота может быть одной из семи основных нот: 'C', 'D', 'E', 'F', 'G', 'A' и 'B'. Она может сопровождаться знаком '+' (диез) или '-' (бемоль). Ноты от 'C' до 'B' формируют октаву, как показано на рисунке ниже. Октава для каждой команды определяется текущей октавой, которая устанавливается командами октавы, описанными далее. Невозможно воспроизвести ноту 'C-' самой низкой октавы (1) или ноту 'B+' самой высокой октавы (8).
Указатель длительности — это одно из следующих чисел: '1', '2', '4', '8', '16', '32', '64' и '128', где '1' обозначает целую ноту, '2' — половинную, '4' — четвертную, '8' — восьмую и так далее. Этот указатель необязателен; если он опущен, длительность будет по умолчанию, установленной командой L (описана ниже). Указатели длительности могут содержать точки рядом с числами. Точка добавляет половину длительности основной ноты. Например, '4.' обозначает длительность '4' (четверть) плюс '8' (восьмая, т.е. половина четверти), или в 1,5 раза длиннее, чем '4'. Возможно, что одна нота имеет более одной точки, где каждая дополнительная точка увеличивает длительность на половину предыдущей. Например, '4..' обозначает длительность '4' плюс '8' плюс '16', '4...' обозначает длительность '4' плюс '8' плюс '16' плюс '32' и так далее. Длительность, увеличенная точками, не может быть короче, чем '128' из-за ограничений компьютера Дика; поэтому ни '128.', ни '32...' не будут приняты. Точки, указанные без чисел, увеличивают длительность по умолчанию. Например, 'C.' эквивалентно 'C4.', когда длительность по умолчанию равна '4'. Обратите внимание, что 'C4C8' и 'C4.' неэквивалентны; первое содержит две разные ноты, в то время как второе — только одну ноту.
Пауза: Rn (n = 1,2,4,8,16,32,64,128 + точки)
Команда R делает паузу на указанную длительность. Длительность должна быть указана так же, как и команды нот, и она также может быть опущена. Обратите внимание, что 'R4R8' и 'R4.' эквивалентны, в отличие от 'C4C8' и 'C4.', так как обе делают паузу на одинаковую длительность '4' плюс '8'.
Октава: On (n = 1-8), <, >
Команда O устанавливает текущую октаву на указанное число. '>' повышает октаву на одну, а '<' понижает на одну. Нельзя установить октаву за пределами диапазона от 1 до 8 с помощью этих команд. Октава изначально установлена на 4.
Длительность по умолчанию: Ln (n = 1,2,4,8,16,32,64,128)
Команда L устанавливает длительность по умолчанию. Длительность должна быть указана так же, как и команды нот, но не может быть опущена или сопровождаться точками. Длительность по умолчанию изначально установлена на 4.
Громкость: Vn (n = 1-255)
Команда V устанавливает текущую громкость. Чем больше, тем громче. Громкость изначально установлена на 100.
Как любитель-композитор, Дик решил воспроизвести свои музыкальные произведения с помощью оператора PLAY. Он написал программу с длинной последовательностью MML и попытался ее запустить, чтобы воспроизвести свою музыку, но столкнулся с неожиданной проблемой: последовательность MML оказалась слишком длинной для обработки в небольшой памяти его компьютера!
Не желая терять все усилия, которые он приложил для использования оператора PLAY, он решил сократить последовательность MML, чтобы она поместилась в памяти. Однако это оказалось для него слишком сложным. Поэтому он попросил вас написать программу, которая для каждой данной последовательности MML выведет самую короткую последовательность MML (т.е. последовательность MML, содержащую минимальное количество символов), которая выражает ту же музыку, что и данная. Обратите внимание, что конечные значения октавы, громкости и длительности по умолчанию могут отличаться от оригинальной последовательности MML.
Входные данные
Входные данные состоят из нескольких наборов данных. Каждый набор данных задается одной строкой, содержащей последовательность MML длиной до 100000 символов. Все последовательности содержат только описанные выше команды. Обратите внимание, что каждая последовательность содержит хотя бы одну ноту, и перед первой нотой и после последней ноты нет паузы.
Конец ввода обозначается строкой, содержащей только "*". Это не является частью какого-либо набора данных и, следовательно, не должно обрабатываться.
Выходные данные
Для каждого тестового случая выведите его номер и самую короткую последовательность MML в строке.
Если существует несколько решений, выведите любое из них.