一个古老的大国正在开发用于军事目的的病毒。目前，他们找到了一种在人类细胞中进行计算的方法。他们设计了一种特殊的酶。这种酶有 4 个结合位点：一个用于读取作为输入的 RNA，一个用于生成作为输出的 RNA，一个用于往复读取和生成 RNA 以保存临时计算状态，最后一个用于往复读取表示程序命令的 RNA。他们需要一些示例程序（RNA）进行演示，却没有足够时间准备，因此请你帮忙。

这种酶在读写 RNA 时，将 3 个核碱基（G、U、A、C）作为一个单元。并非全部 $4^3=64$ 种组合都会使用。他们只选了 $11$ 种，将其解释为数值数据或命令。

这 $11$ 种组合如下：

酶的输入结合位点一旦附着到 RNA 链上，计算过程就开始了。酶将输入结合位点移到输入 RNA 的第一个数据单元，将程序结合位点移到程序 RNA 的第一个代码单元，将输出结合位点初始化为空，并生成只含一个单元的 RNA，将状态结合位点初始化到该单元。

酶逐个执行程序命令，直到遇到称为“STOP 标记”的命令。

程序命令非常简单，与现代编程语言很不一样。一共只有 9 种命令：

1. STOP 标记。停止执行。

2. 将状态结合位点移到下一个单元。如果越过最后一个单元，则放入一个值为 $0$ 的单元。

3. 将状态结合位点移到上一个单元。如果越过第一个单元，则放入一个值为 $0$ 的单元。

4. 将状态结合位点下的数据单元替换为数值更大的下一个单元。如果超过最大值（$9$），则替换为 $-1$。

5. 将状态结合位点下的数据单元替换为数值更小的下一个单元。如果低于最小值（$-1$），则替换为 $9$。

6. 将状态结合位点下的数据单元复制到输出位点。

7. 如果没有输入数据单元，则将状态结合位点下的数据单元替换为 $-1$。否则，将它替换为输入位点下的数据单元，并将输入结合位点移到下一个数据单元。

8. 如果状态结合位点下的数据单元不为 $0$，则将程序结合位点移到下一条命令。否则，向前移到与其“匹配”的命令 $8$ 之后的命令。

9. 如果状态结合位点下的数据单元为 $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

说明

每份样例输出只有一行。由于纸张排版，我们在样例中将它分成了多行。你应当把它们拼接成一行。

下面是第一个样例程序的运行示例。