P9763 [ROIR 2021] Gene Mutation (Day 1)

**Translated from [ROIR 2021](http://neerc.ifmo.ru/school/archive/2020-2021.html) Day 1 T3 [ Изменённая ДНК](http://neerc.ifmo.ru/school/archive/2020-2021/ru-olymp-regional-2021-day1.pdf)**。

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'$.

One line containing a string $T$.

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`.

[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$. | Subtask ID | Constraints | Points | |:-:|:-:|:-:| | $1$ | $\lvert T\rvert\le \lvert S\rvert\le 10$ | $9$ | | $2$ | $\lvert T\rvert\le 100$, $\lvert S\rvert\le 10^4$ | $17$ | | $3$ | $\lvert T\rvert\le 10^3$, $\lvert S\rvert\le 10^5$ | $21$ | | $4$ | $\lvert S\rvert\le 10^7$ | $11$ | | $5$ | No special constraints | $42$ | Translated by ChatGPT 5