Задача 3. Изменённая ДНК

Автор:Олег Христенко   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Биологи обнаружили новый живой организм и решили изучить его ДНК. ДНК кодируется последовательностью символов "A", "G", "C" и "T".

Так как строка, кодирующая ДНК, часто очень длинная, для её хранения применяют RLE-кодирование. А именно, каждый блок, состоящий из двух или более идущих подряд одинаковых символов, заменяется на число, равное длине этого блока, после которого записывается соответствующий символ. Например, последовательность "AAAGGTCCA" в закодированной форме имеет вид "3A2GT2CA".

В результате экспериментов, проводимых в лаборатории, ДНК может мутировать. Каждая мутация — это либо удаление одного символа из последовательности, либо добавление одного символа, либо замена одного символа на другой.

Уходя вечером из лаборатории, учёный записал ДНК в закодированной форме. Когда он вернулся на работу утром, он обнаружил, что в ДНК произошла ровно одна мутация. Теперь ученых интересует, какая минимальная и максимальная длина может получиться у новой ДНК в закодированной форме.

Требуется по заданной ДНК в закодированной форме определить, какая мутация может привести к тому, что у новой ДНК будет закодированная форма минимальной возможной длины, а какая — к тому, что у новой ДНК будет закодированная форма максимальной возможной длины.

Формат входных данных

В единственной строке входа находится строка s, состоящая из цифр и букв "A", "G", "C" и "T" — закодированная ДНК.

Гарантируется, что это строка является корректной закодированной записью некоторой строки из символов "A", "G", "C" и "T".

Формат выходных данных

В первой строке выведите мутацию, после которой закодированная строка имеет минимальную длину. Выведите:

В следующей строке выведите мутацию, после которой закодированная строка имеет максимальную длину, в таком же формате.

Если подходящих ответов несколько, можно вывести любой из них.

Ограничения

Обозначим за n длину закодированной строки, а за L длину исходной строки.

1 ≤ n ≤ 105, 1 ≤ L ≤ 109

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача Баллы Доп. ограничения Необходимые подзадачи Информация о проверке
191 ≤ n ≤ L ≤ 10полная
2171 ≤ n ≤ 100, 1 ≤ L ≤ 1041первая ошибка
3211 ≤ n ≤ 1000, 1 ≤ L ≤ 1051, 2первая ошибка
4111 ≤ n ≤ 105, 1 ≤ L ≤ 1071--3первая ошибка
5421 ≤ n ≤ 105, 1 ≤ L ≤ 1091--4первая ошибка

Пояснение к примеру

Исходная последовательность имела вид "AAAAACAAAAACC".

Первая операция превращает её в последовательность "AAAAAAAAAAACC", которая кодируется как "11A2C". Эта закодированная последовательность имеет минимальную возможную для этого теста длину, равную 5.

Вторая операция превращает её в последовательность "AACAAACAAAAACC", которая кодируется как "2AC3AC5A2C". Эта закодированная последовательность имеет максимальную возможную для этого теста длину, равную 10.

Примеры тестов

Стандартный вход Стандартный выход
1
5AC5A2C
3 6 A
1 2 C

0.117s 0.026s 13