随着技术和太空探索的不断进步，人类正在向比以往更多的行星和卫星发射探测器。其中一个探测器目前位于火卫一（Phobos，火星的两颗卫星之一）。该探测器向地球传回二进制数据，但它只能在每隔几个小时的短暂时间窗口内进行传输。它快速的轨道、微小的体积以及与火星的极近距离，意味着火星在大部分时间里会物理性地阻挡在探测器和地球之间，从而屏蔽无线电波。在一次数据传输的时间窗口内，会传输一个包含 $n$ 个二进制位的巨大数据包，这正好是该时间窗口内所能传输的最大数据量。

火星及其两颗卫星火卫一和火卫二，图片来自 NASA’s Goddard Space Flight Center / JPL-Caltech / GSFC / Univ. of Arizona on NASA

该探测器已经部署了几年，因此机械问题开始接踵而至。最近一个非常棘手的问题是车载时钟变得不可靠，这很可能是由大约 $-112^\circ$ 到 $-4^\circ$ 摄氏度之间剧烈且频繁的温度波动引起的。结果，探测器在错误的时间发送了数据包，此时无线电波无法到达地球。为了缓解这一问题，探测器现在会连续多次发送其数据包。

尽管这使得地球接收到了 $n$ 位的数据，但研究人员无法确定数据包的起点和终点，从而使数据变得毫无用处。接收到的数据由发送数据的一个可能为空的后缀，后跟发送数据的一个前缀组成，总长度恰好为 $n$ 位。例如，如果原始数据包是 “00101001”，接收到的数据可能是 “00100101”（颜色仅用于视觉区分）。

你需要编写软件，在传输前将数据编码为相同长度的信息，以便在收到损坏的数据包后能够对其进行解码。幸运的是，工程部门成功改进了接收天线的设计，提高了信噪比，因此你现在可以在无线电传输中使用由三个可区分符号组成的字符集，而不再仅仅是两个。

对于每个测试用例，你的程序将被运行两次。在第一次运行（pass）中，你的程序将获得一个待编码的二进制字符串。在第二次运行中，你的程序将获得你在第一次运行中编码后的字符串，该字符串可能已经按照上述方式进行了修改。解码该字符串以恢复第一次运行时的输入。

提供了一个测试工具以帮助开发你的解决方案。

输入格式

输入包含：

• 第一行包含 “Encode” 或 “Decode”，取决于你需要执行的操作。
• 第二行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示数据包的大小。
• 第三行包含一个长度为 $n$ 的字符串 $s$，表示数据包。

在编码阶段，该字符串由符号 ‘0’ 和 ‘1’ 组成。

在解码阶段，该字符串将是你编码后的三进制字符串的一个循环移位。换句话说，该字符串是你在编码阶段打印的字符串，可能经过了修改以反映该数据包在地球上是如何被接收的（如题目描述中所述）。

输出格式

在编码阶段，输出使用符号 ‘0’、‘1’ 和 ‘2’ 编码的长度为 $n$ 的字符串。

在解码阶段，输出原始的二进制字符串，即编码阶段输入的数据包。

样例

输入样例 1 (第一次运行)

Encode
3
001

输出样例 1 (第一次运行)

002

输入样例 1 (第二次运行)

Decode
3
200

输出样例 1 (第二次运行)

001

说明 1

在第一个样例中，编码后的三进制字符串 “002” 被接收为 “200”。

输入样例 2 (第一次运行)

Encode
4
0100

输出样例 2 (第一次运行)

2100

输入样例 2 (第二次运行)

Decode
4
2100

输出样例 2 (第二次运行)

0100

说明 2

在第二个样例中，编码后的三进制字符串在接收时与编码时完全一致。