K - encode/decode

以下の２条件を全て満たす文字列Tの事を「良い」文字列と呼ぶことにする

• TはABCDEFGHIの9種類の文字列からなる
• T上の連続する２文字は次のグラフ上でも隣接している

「良い」文字列の例

• BEB
• ABCDCBEFGHI

「良い」文字列ではない例

• AC(AとCは隣接していない)
• AABCD(同じ文字はグラフ上では隣接していないとみなす)

以下の条件を満たすような２つの関数,encodeとdecodeを実装せよ.

• 任意の01列Sに対し,encode(S)は「良い」文字列である
• 任意の01列Sに対し,decode(encode(S))=Sを満たす

入出力形式

この問題にはencodeフェーズとdecodeフェーズがあり, それぞれ独立にプログラムが実行される.

encodeフェーズのとき, 入力は以下の形式で与えられる.

encode
N
S

Nは与えられる01列Sの長さである. Sはあなたがencodeするべき01列である. この時の,あなたが提出するプログラムの出力をTとする. Tが良い文字列でない場合は不正解となり,decodeフェーズは実行されない. decodeフェーズのとき,入力は以下の形式で与えられる.

decode
M
T

Tはencodeフェーズにおけるあなたの出力である. Mは文字列Tの長さである. この時の,あなたが提出するプログラムの出力がencodeフェーズにおけるSと一致する場合,正解となる

採点方式

この問題では入力Sに対する出力encode(S)の長さに応じて得点が決まる.

全てのテストケースについて, |encode(S)| ≦ |S| + 10 を満たすときこの問題に対する得点が満点となる.

また, |encode(S)| ≦ 2×|S| + 10 を満たす場合, この問題に対する得点は50点となる.

制約

• 1 ≤ N ≤ 300000

入出力例

encodeフェーズ

入力

encode
6
001100

出力

ABCBE

encodeフェーズの終了後あなたのプログラムは一旦終了し,次にdecodeフェーズが開始する

decodeフェーズ

入力

decode
5
ABCBE

出力

001100