Wielki, stary kraj rozwija wirusy do celów wojskowych. Obecnie odkrył sposób wykonywania obliczeń w ludzkich komórkach. Zaprojektowano specjalny enzym z 4 miejscami wiązania. Jedno odczytuje wejściowe RNA, drugie wytwarza wyjściowe RNA. Kolejne odczytuje i wytwarza RNA w obu kierunkach, przechowując tymczasowy stan obliczeń, a ostatnie odczytuje w obu kierunkach RNA zawierające polecenia programu. Potrzebne są przykładowe programy (RNA) do demonstracji. Brakuje czasu na ich przygotowanie, więc poproszono Cię o pomoc.

Przy odczytywaniu i zapisywaniu RNA enzym traktuje 3 zasady azotowe (G,U,A,C) jako jednostkę. Nie wykorzystuje wszystkich $4^3=64$ kombinacji. Wybrano tylko $11$, interpretowanych jako dane liczbowe lub polecenia.

Te $11$ kombinacji to:

Gdy wejściowe miejsce wiązania enzymu przyczepi się do łańcucha RNA, rozpoczynają się obliczenia. Enzym przesuwa je do pierwszej jednostki danych wejściowego RNA, miejsce wiązania programu do pierwszej jednostki kodu RNA programu i inicjalizuje wyjściowe miejsce wiązania jako puste. Wytwarza też RNA z jedną jednostką i inicjalizuje na niej miejsce wiązania stanu.

Enzym wykonuje polecenia kolejno, aż dotrze do polecenia zwanego „znacznikiem STOP”.

Polecenia są bardzo proste i mocno różnią się od współczesnych języków programowania. Jest ich tylko 9 rodzajów:

1. Znacznik STOP. Zakończ wykonanie.

2. Przesuń miejsce wiązania stanu do następnej jednostki. Jeśli jest za ostatnią, wstaw jednostkę $0$.

3. Przesuń miejsce wiązania stanu do poprzedniej jednostki. Jeśli jest przed pierwszą, wstaw jednostkę $0$.

4. Zastąp jednostkę danych w miejscu wiązania stanu następną większą liczbowo. Jeśli przekroczy największą wartość ($9$), zastąp ją przez $-1$.

5. Zastąp jednostkę danych w miejscu wiązania stanu następną mniejszą liczbowo. Jeśli spadnie poniżej najmniejszej wartości ($-1$), zastąp ją przez $9$.

6. Skopiuj jednostkę danych z miejsca wiązania stanu do miejsca wyjściowego.

7. Jeśli nie ma jednostek danych wejściowych, zastąp jednostkę w miejscu wiązania stanu przez $-1$. W przeciwnym razie zastąp ją jednostką w miejscu wejściowym i przesuń wejściowe miejsce wiązania do następnej jednostki danych.

8. Jeśli jednostka w miejscu wiązania stanu jest różna od $0$, przesuń miejsce wiązania programu do następnego polecenia. W przeciwnym razie przesuń je do przodu, do polecenia po „pasującym” poleceniu $8$.

9. Jeśli jednostka w miejscu wiązania stanu jest równa $0$, przesuń miejsce wiązania programu do następnego polecenia. W przeciwnym razie przesuń je wstecz, do polecenia po „pasującym” poleceniu $7$.

„Pasujące” oznacza traktowanie poleceń $7$ i $8$ jako nawiasów ( i ). Powinny tworzyć poprawne wyrażenie nawiasowe, a pasujące polecenia odpowiadają pasującym nawiasom. Para poleceń $7$ i $8$ jest często używana jako pętla.

Po wykonaniu bieżącego polecenia miejsce wiązania programu przesuwa się do następnego, z wyjątkiem poleceń $0,7,8$.

Zadanie demonstracyjne jest proste: odczytaj ciąg nieujemnych cyfr jako liczbę dziesiętną i ustal, czy jest wielokrotnością $k$. Ponadto długość programu i liczba kroków wykonania nie powinny przekraczać $10^6$.

Przygotowano dla Ciebie symulator (simu.c). Pierwszy wiersz wejścia symulatora to program RNA. Kolejne wiersze są wejściowymi RNA dla tego programu. Symbol - oznacza $-1$, a symbole od 0 do 9 oznaczają od $0$ do $9$. Symulator uruchamia program dla każdych danych wejściowych i wypisuje końcowy wynik oraz liczbę kroków. Przyjmuje też specjalne polecenie $9$: po każdym dotarciu do niego wypisuje bieżący wynik, dane stanu i liczbę kroków. Wykonanie polecenia $9$ nie jest liczone jako krok.

Uwagi

• Kod symulatora można pobrać z załączników w DOMjudge. Znajdziesz go tutaj.

• Symulator oceniający zgłoszenia nie akceptuje polecenia $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;
}

Wejście

Jedyny wiersz zawiera dodatnią liczbę całkowitą $k$.

Ograniczenia

• $1\le k\le6$

• $1\le n\le10^9$

Wyjście

Plik wyjściowy powinien zawierać jeden wiersz będący RNA poleceń.

Ten program odczyta ciąg nieujemnych cyfr jako dziesiętną liczbę całkowitą $n$. Jeśli $n$ jest wielokrotnością $k$, wypisze $1$, w przeciwnym razie $0$.

Twój program bezpośrednio czyta i zapisuje dane liczbowe. Enzym przekształca je na zasady azotowe i odwrotnie.

Długość kodu RNA nie powinna przekraczać $10^6$. Liczba kroków wykonania nie powinna przekraczać $10^6$.

Przykład

Wejście 1

1

Wyjście 1

UCCAGGUACUGUUGCGCGCCC

Wejście 2

2

Wyjście 2

UGCAGGUACACGAGGUACUGUUGAAGGUACACGUGCUGAUGUUCCUGCUGUACGUGCAGGUACUGAUGCACGAGGUACUGAUACACGAGGUACUGAUGCACGAGGUACUGAUACACGAGGUACUGAUGCACGAGGUACUGAUACACGAGGUACUGAUGCACGAGGUACUGAUACACGAGGUACUGAUGCACGAGGUACUGAUACACGUGUUGUUGUUGUUGUUGUUGUUGUUGUUGUUGAGCGCCC

Wejście 3

3

Wyjście 3

UGCAGGACGACGUCCAGGUACACGUGCACGUGCUGAUGAUGUACGACGACGUGCUGAUGCAGGUACACGAGGUACUGUUGAUGUACGAGGUGAUGAUGAUGCUGAAGGUACACGAGGUACUGUUGAUGUACGGCGCCCUGUUGAUGAAGGUACUGAUGCACGAGGUACUGAUGCACGAGGUACUGAUACUACACGAGGUACUGAUGCACGAGGUACUGAUGCACGAGGUACUGAUACUACACGAGGUACUGAUGCACGAGGUACUGAUGCACGAGGUACUGAUACUACACGUGUUGUUGUUGUUGUUGUUGUUGUUGUUGAAGGUACUGAUGCACGUGUUGAAGGUACACGUGCUGAAGGUACACGUGCUGAAGGUACACGUACUACUGAAGGUACACGUGCUGAUGUUGUUGUUGUACGAGGUACUGAUGCACGUGUUGAUGAUGU

Wejście 4

6

Wyjście 4

UGCAGGACGACGUCCAGGUACACGUGCACGUGCUGAUGAUGUACGACGACGUGCUGAUGCAGGUACACGAGGUACUGUUGAUGUACGAGGUGAUGAUGAUGAAGGAGGUACUGUGCGCCCUGUACGACGACGACGACGACGUGCAGGUACUGAUGCACGAGGUACUGAUACACGAGGUACUGAUGCACGAGGUACUGAUACACGAGGUACUGAUGCACGAGGUACUGAUACACGAGGUACUGAUGCACGAGGUACUGAUACACGAGGUACUGAUGCACGAGGUACUGAUACACGUGUUGUUGUUGUUGUUGUUGUUGUUGUUGUUGAGCGCCCUGUUGAACGACGAGGUACUGUACGAGGUACUGUUGAUGAUGAUGAAGGUACACGACGACGUGCACGUGCUGAUGAUGAUGAUGUACGACGACGAGGUACUGAUGAUGAUGCACGACGACGUGUUGAUGAUGAAGGUACUGAUGCACGAGGUACUGAUGCACGAGGUACUGAUACUACACGAGGUACUGAUGCACGAGGUACUGAUGCACGAGGUACUGAUACUACACGAGGUACUGAUGCACGAGGUACUGAUGCACGAGGUACUGAUACUACACGUGUUGUUGUUGUUGUUGUUGUUGUUGUUGAAGGUACUGAUGCACGUGUUGAAGGUACACGUGCUGAAGGUACACGUGCUGAAGGUACACGUACUACUGAAGGUACACGUGCUGAUGUUGUUGUUGUACGAGGUACUGAUGCACGUGUUGAUGAUGU

Uwagi

Każde przykładowe wyjście ma tylko jeden wiersz. Podzieliliśmy je na wiersze ze względu na układ strony. Należy połączyć je w jeden wiersz.

Poniżej znajduje się przykład wykonania pierwszego przykładowego programu.