一个古老的大国正在开发用于军事目的的病毒。目前，他们找到了一种在人类细胞中进行计算的方法。他们设计了一种特殊的酶。这种酶有 4 个结合位点：一个用于读取作为输入的 RNA，一个用于生成作为输出的 RNA，一个用于往复读取和生成 RNA 以保存临时计算状态，最后一个用于往复读取表示程序命令的 RNA。他们需要一些示例程序（RNA）进行演示，却没有足够时间准备，因此请你帮忙。
这种酶在读写 RNA 时，将 3 个核碱基（G、U、A、C）作为一个单元。并非全部 $4^3=64$ 种组合都会使用。他们只选了 $11$ 种，将其解释为数值数据或命令。
这 $11$ 种组合如下：
| 核碱基 | 值 | 命令 |
|---|---|---|
| GAC | $-1$ | |
| CCC | $0$ | STOP |
| ACG | $1$ | NEXT |
| UGA | $2$ | PREV |
| UGC | $3$ | INC |
| UAC | $4$ | DEC |
| GCG | $5$ | OUT |
| UCC | $6$ | IN |
| AGG | $7$ | BEGIN |
| UGU | $8$ | END |
| CAC | $9$ | (DEBUG) |
酶的输入结合位点一旦附着到 RNA 链上，计算过程就开始了。酶将输入结合位点移到输入 RNA 的第一个数据单元，将程序结合位点移到程序 RNA 的第一个代码单元，将输出结合位点初始化为空，并生成只含一个单元的 RNA，将状态结合位点初始化到该单元。
酶逐个执行程序命令，直到遇到称为“STOP 标记”的命令。
程序命令非常简单，与现代编程语言很不一样。一共只有 9 种命令：
STOP 标记。停止执行。
将状态结合位点移到下一个单元。如果越过最后一个单元，则放入一个值为 $0$ 的单元。
将状态结合位点移到上一个单元。如果越过第一个单元，则放入一个值为 $0$ 的单元。
将状态结合位点下的数据单元替换为数值更大的下一个单元。如果超过最大值（$9$），则替换为 $-1$。
将状态结合位点下的数据单元替换为数值更小的下一个单元。如果低于最小值（$-1$），则替换为 $9$。
将状态结合位点下的数据单元复制到输出位点。
如果没有输入数据单元，则将状态结合位点下的数据单元替换为 $-1$。否则，将它替换为输入位点下的数据单元，并将输入结合位点移到下一个数据单元。
如果状态结合位点下的数据单元不为 $0$，则将程序结合位点移到下一条命令。否则，向前移到与其“匹配”的命令 $8$ 之后的命令。
如果状态结合位点下的数据单元为 $0$，则将程序结合位点移到下一条命令。否则，向后移到与其“匹配”的命令 $7$ 之后的命令。
“匹配”指将命令 $7$ 和命令 $8$ 视为括号 ( 和 )。它们应当构成合法的配对表达式，匹配的命令对应于匹配的括号。配对的命令 $7$ 和 $8$ 常用于循环。
除命令 $0,7,8$ 外，执行当前命令后，程序结合位点会移到下一条命令。
演示问题很简单：将一串非负数字作为十进制数读入，并判断它是否为 $k$ 的倍数。此外，程序长度和执行步数都不得超过 $10^6$。
他们为你准备了模拟程序（simu.c）。模拟器输入的第一行是 RNA 程序，后续各行是该程序的输入 RNA。输入中用 - 表示 $-1$，用 0 到 9 表示 $0$ 到 $9$。模拟器会对每份输入数据执行程序，并输出最终结果和执行步数。模拟器还接受特殊命令 $9$，每次执行到命令 $9$ 时，会输出当前结果、状态数据和执行步数。命令 $9$ 的执行不计入步数。
说明
可以在 DOMjudge 的附件中下载模拟器源代码，也可以在这里找到。
用于评测提交的模拟器不接受命令 $9$。
/* simu.c */
/* gcc -o simu simu.c */
#include <stdio.h>
#include <string.h>
char *cmds[10] =
{ "CCC", "ACG", "UGA", "UGC", "UAC"
, "GCG", "UCC", "AGG", "UGU", "CAC"
};
char code[1000002], memory[2000001], input[1000001];
static inline int get_cmd(char *code){
for(int i=9; i>=0; --i)
if( strncmp(cmds[i], code, 3)==0 )
return i;
return -1;
}
int main(){
if( !fgets(code, 1000002, stdin) ){
puts("no code");
return 1;
}
int code_len = strlen(code);
if( code[code_len-1]!='\n' ){
puts("code too long");
return 1;
}
code[--code_len] = 0;
while( fgets(input, 1000001, stdin) ){
char *ip = code, *input_p = input;
char *mem = memory + 1000000;
char *mem_begin=mem, *mem_end=mem;
*mem = 0;
int step = 0, eof = 0;
while(1){
if( step == 1000000 ){
puts("step out of bound");
break;
}
if( code+code_len-ip < 3 ){
puts("code out of bound");
break;
}
int cmd = get_cmd(ip);
if( cmd<0 ){
printf("invalid code point: %c%c%c\n",
ip[0], ip[1], ip[2]);
break;
}
if( cmd==0 ){
puts("stop normally");
break;
}
if( cmd==1 ){
++mem;
if( mem>mem_end )
*++mem_end = 0;
}
else if( cmd==2 ){
--mem;
if( mem<mem_begin )
*--mem_begin = 0;
}
else if( cmd==3 ){
if( *mem==9 )
*mem = -1;
else
++*mem;
}
else if( cmd==4 ){
if( *mem==-1 )
*mem = 9;
else
--*mem;
}
else if( cmd==5 ){
if( *mem==-1 )
putchar('-');
else
putchar('0' + *mem);
}
else if( cmd==6 ){
while(1){
if( !*input_p || *input_p=='\n' ){
*mem = -1;
break;
}
if( *input_p=='-' ){
*mem = -1;
++input_p;
break;
}
if( '0'<=*input_p && *input_p<='9' ){
*mem = *input_p++ - '0';
break;
}
++input_p;
}
}
else if( cmd==7 ){
if( !*mem ){
int skip = 1;
while(skip){
ip += 3;
if( code+code_len-ip < 3 ){
puts("7 can't find matched 8");
goto END;
}
if( strncmp(cmds[8], ip, 3)==0 )
--skip;
else if( strncmp(cmds[7], ip, 3)==0 )
++skip;
}
}
}
else if( cmd==8 ){
if( *mem ){
int skip = 1;
while(skip){
ip -= 3;
if( ip < code ){
puts("8 can't find matched 7");
goto END;
}
if( strncmp(cmds[7], ip, 3)==0 )
--skip;
else if( strncmp(cmds[8], ip, 3)==0 )
++skip;
}
}
}
else if( cmd==9 ){
printf("\nstep: %d, state: ", step);
for(char *p=mem_begin; p<=mem_end; ++p)
if( p==mem )
printf("[%c]", *p<0 ? '-' : '0'+*p);
else
putchar(*p<0 ? '-' : '0'+*p);
printf(", code:");
for(char *p=code; p<code+code_len; p+=3)
printf("%c%c%c%c",
p==ip ? '[' : p==ip+3 ? ']' : ' ',
p[0], p[1], p[2]);
if( code+code_len==ip+3 )
putchar(']');
puts("");
--step;
}
++step;
ip += 3;
}
END:;
}
return 0;
}输入格式
唯一一行包含一个正整数 $k$。
数据范围
$1\le k\le6$
$1\le n\le10^9$
输出格式
输出文件应包含一行，即命令 RNA。
该程序会将一串非负数字作为十进制整数 $n$ 读入。如果 $n$ 是 $k$ 的倍数，则输出 $1$；否则输出 $0$。
你的程序直接读写数值数据。酶会在数值数据与核碱基之间进行转换。
RNA 代码长度不得超过 $10^6$，执行步数不得超过 $10^6$。
样例
输入格式 1
1
输出格式 1
UCCAGGUACUGUUGCGCGCCC
输入格式 2
2
输出格式 2
UGCAGGUACACGAGGUACUGUUGAAGGUACACGUGCUGAUGUUCCUGCUGUACGUGCAGGUACUGAUGCACGAGGUACUGAUACACGAGGUACUGAUGCACGAGGUACUGAUACACGAGGUACUGAUGCACGAGGUACUGAUACACGAGGUACUGAUGCACGAGGUACUGAUACACGAGGUACUGAUGCACGAGGUACUGAUACACGUGUUGUUGUUGUUGUUGUUGUUGUUGUUGUUGAGCGCCC
输入格式 3
3
输出格式 3
UGCAGGACGACGUCCAGGUACACGUGCACGUGCUGAUGAUGUACGACGACGUGCUGAUGCAGGUACACGAGGUACUGUUGAUGUACGAGGUGAUGAUGAUGCUGAAGGUACACGAGGUACUGUUGAUGUACGGCGCCCUGUUGAUGAAGGUACUGAUGCACGAGGUACUGAUGCACGAGGUACUGAUACUACACGAGGUACUGAUGCACGAGGUACUGAUGCACGAGGUACUGAUACUACACGAGGUACUGAUGCACGAGGUACUGAUGCACGAGGUACUGAUACUACACGUGUUGUUGUUGUUGUUGUUGUUGUUGUUGAAGGUACUGAUGCACGUGUUGAAGGUACACGUGCUGAAGGUACACGUGCUGAAGGUACACGUACUACUGAAGGUACACGUGCUGAUGUUGUUGUUGUACGAGGUACUGAUGCACGUGUUGAUGAUGU
输入格式 4
6
输出格式 4
UGCAGGACGACGUCCAGGUACACGUGCACGUGCUGAUGAUGUACGACGACGUGCUGAUGCAGGUACACGAGGUACUGUUGAUGUACGAGGUGAUGAUGAUGAAGGAGGUACUGUGCGCCCUGUACGACGACGACGACGACGUGCAGGUACUGAUGCACGAGGUACUGAUACACGAGGUACUGAUGCACGAGGUACUGAUACACGAGGUACUGAUGCACGAGGUACUGAUACACGAGGUACUGAUGCACGAGGUACUGAUACACGAGGUACUGAUGCACGAGGUACUGAUACACGUGUUGUUGUUGUUGUUGUUGUUGUUGUUGUUGAGCGCCCUGUUGAACGACGAGGUACUGUACGAGGUACUGUUGAUGAUGAUGAAGGUACACGACGACGUGCACGUGCUGAUGAUGAUGAUGUACGACGACGAGGUACUGAUGAUGAUGCACGACGACGUGUUGAUGAUGAAGGUACUGAUGCACGAGGUACUGAUGCACGAGGUACUGAUACUACACGAGGUACUGAUGCACGAGGUACUGAUGCACGAGGUACUGAUACUACACGAGGUACUGAUGCACGAGGUACUGAUGCACGAGGUACUGAUACUACACGUGUUGUUGUUGUUGUUGUUGUUGUUGUUGAAGGUACUGAUGCACGUGUUGAAGGUACACGUGCUGAAGGUACACGUGCUGAAGGUACACGUACUACUGAAGGUACACGUGCUGAUGUUGUUGUUGUACGAGGUACUGAUGCACGUGUUGAUGAUGU
说明
每份样例输出只有一行。由于纸张排版，我们在样例中将它分成了多行。你应当把它们拼接成一行。
下面是第一个样例程序的运行示例。
| 程序 | 内存 | 输入 | 输出 | 注释 |
|---|---|---|---|---|
| UCC AGG UAC UGU UGC GCG CCC | $3$ | |||
| UCC AGG UAC UGU UGC GCG CCC | $3$ | IN | ||
| UCC AGG UAC UGU UGC GCG CCC | $3$ | BEGIN: $3 e0$ | ||
| UCC AGG UAC UGU UGC GCG CCC | $2$ | DEC | ||
| UCC AGG UAC UGU UGC GCG CCC | $2$ | END: $2 e0$ | ||
| UCC AGG UAC UGU UGC GCG CCC | $1$ | DEC | ||
| UCC AGG UAC UGU UGC GCG CCC | $1$ | END: $1 e0$ | ||
| UCC AGG UAC UGU UGC GCG CCC | $0$ | DEC | ||
| UCC AGG UAC UGU UGC GCG CCC | $0$ | END: $0=0$ | ||
| UCC AGG UAC UGU UGC GCG CCC | $1$ | INC | ||
| UCC AGG UAC UGU UGC GCG CCC | $1$ | $1$ | OUT | |
| UCC AGG UAC UGU UGC GCG CCC | $1$ | $1$ | STOP |