题目描述

生物学家发现了一种新的生物，并决定研究它的 DNA。DNA 用只包含 A、G、C、T 的字符串表示。

由于 DNA 字符串通常很长，科学家使用 RLE 编码来存储它。具体来说，每个由两个或更多连续相同字符组成的块，会被替换为“块长度 + 对应字符”。长度为 $1$ 的块则只保留字符本身。

例如，序列：

AAAGGTCCA

编码后为：

3A2GT2CA

实验过程中，DNA 可能发生变异。一次变异恰好是以下三种操作之一：

1. 删除序列中的一个字符；
2. 插入一个字符；
3. 将一个字符替换成另一个字符。

某位科学家晚上离开实验室时，把 DNA 以编码形式记录下来。第二天早上回来时，他发现 DNA 恰好发生了一次变异。

现在需要确定：通过一次变异，新 DNA 的编码长度最短可能是多少、最长可能是多少。你需要输出一种使编码长度达到最小的变异，以及一种使编码长度达到最大的变异。

输入格式

输入一行字符串 $s$，由数字以及字母 A、G、C、T 构成，表示原 DNA 的 RLE 编码。

保证 $s$ 是某个合法 DNA 字符串的正确编码。

输出格式

第一行输出一种使变异后编码长度最小的操作。

第二行输出一种使变异后编码长度最大的操作。

操作格式如下：

• 1 x Z：插入字符 $Z$，使其左侧恰好有 $x$ 个原来的字符。$Z\in\{A,C,G,T\}$；
• 2 x：删除原序列中编号为 $x$ 的字符；
• 3 x Z：将原序列中编号为 $x$ 的字符替换为 $Z$，其中 $Z\in\{A,C,G,T\}$，且原字符必须不等于 $Z$。

删除和替换中的位置 $x$ 按原始未编码 DNA 序列从 $1$ 开始编号。插入操作中的 $x$ 可以为 $0$，表示插在最前面。

如果存在多个合法答案，可以输出任意一个。

数据范围

设 $n$ 为编码字符串长度，$L$ 为原始 DNA 字符串长度。

子任务

样例输入

5AC5A2C

样例输出

3 6 A
1 2 C

样例解释

原始序列为：

AAAAACAAAAACC

第一种操作会将它变成：

AAAAAAAAAAACC

其编码为：

11A2C

这是该测试下可能得到的最短编码，长度为 $5$。

第二种操作会将它变成：

AACAAACAAAAACC

其编码为：

2AC3AC5A2C

这是该测试下可能得到的最长编码，长度为 $10$。