24869번 - Изменённая ДНК 서브태스크스페셜 저지다국어

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

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

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

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

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

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

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

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

• 1 $x$ Z,  если надо вставить символ Z так, чтобы слева от него было ровно $x$ старых символов. Символ Z должен быть из множества {A, C, G, T}.
• 2 $x$, если надо удалить символ с номером $x$ из последовательности.
• 3 $x$ Z, если надо заменить символ с номером $x$ заменить на символ Z. Символ Z должен быть из множества {A, C, G, T}. При этом на этом месте до мутации обязательно должен был находиться символ, не равный Z. 

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

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

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

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

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