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

시간 제한1초메모리 제한512 MB

요약

RLE로 압축된 DNA 문자열이 주어질 때, 한 번의 삽입, 삭제, 치환으로 다시 압축했을 때 길이가 최소가 되는 경우와 최대가 되는 경우를 각각 찾는다.

난이도: 보통10점 중 7점
유형: 문자열, 구현, 그리디, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

Биологи обнаружили новый живой организм и решили изучить его ДНК. ДНК кодируется последовательностью символов <<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$ .

예제1

예제 1
입력
```
5AC5A2C
```
예상 출력
```
3 6 A
1 2 C
```