Background

Translated from ROIR 2021 Day 1 T3 Изменённая ДНК。

Problem Description

We define that a valid gene string contains only A, G, C, and T.

We define that any valid gene string has a compressed string. The compressed string replaces each maximal consecutive block of the same letter in the original gene string with: the number of occurrences followed by that letter. If the number is $1$, the number is omitted.

Example: the compressed string of AAAAACAAAAACC is 5AC5A2C.

Now you are given a valid gene string $S$, whose compressed string is $T$. You may perform exactly one operation on $S$. The operation can be one of the following three types:

• Insert a character $Z$ after the $x$-th character of $S$.
• Delete the $x$-th character of $S$.
• Replace the $x$-th character of $S$ with another character $Z$.

Let $S$ become $S'$ after the operation, and let the compressed string of $S'$ be $T'$. Find one operation plan that minimizes the length of $T'$, and one operation plan that maximizes the length of $T'$.

Input Format

One line containing a string $T$.

Output Format

Output two lines in total. The first line is one plan that minimizes the length of $T'$. The second line is one plan that maximizes the length of $T'$.

The output format for a plan is as follows:

• If you want to use operation $1$, output in the form 1 x Z.
• If you want to use operation $2$, output in the form 2 x.
• If you want to use operation $3$, output in the form 3 x Z.

5AC5A2C

3 6 A
1 2 C

Hint

[Sample Explanation]:

$S=$ AAAAACAAAAACC.

After applying operation 3 6 A, we have $S'=$ AAAAAAAAAAACC, and $T'=$ 11A2C.

After applying operation 1 2 C, we have $S'=$ AACAAACAAAAACC, and $T'=$ 2AC3AC5A2C.

[Constraints]:

For all subtasks, $1\le |T|\le 10^5$, $1\le |S|\le 10^9$.

Translated by ChatGPT 5