cho.sh

Изменённая ДНК

아직 제출이 없습니다시간 제한1초메모리 제한512 MB

문제

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

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

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

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

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

입력

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

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

출력

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

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

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

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

힌트

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

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

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