#include<stack>
#include<cstdio>
#include<stdio.h>
#include<iostream>
#include<math.h>
#include<set>
#include<sstream>
#include<cctype>
#include<string>
#include<cstring>
#include<map>
#include<algorithm>
using namespace std;
#define ll long long 
#define pf printf
#define sf scanf

//int main()
//{
//    
//    int i, j;
//    char s[10000];
//    string temp = "";
//    while (1){
//        gets(s);
//        if (s[0] == '#')break;
//        set<string> d;
//        d.clear();
//        set<string>::iterator ite;
//        int len = strlen(s);
//        s[len] = ' '; s[len + 1] = '\0';
//        len++;
//        string str = "";
//        for (i = 0; i < len; ++i){
//            if (s[i] == ' '){
//                if (str.length()){
//                    d.insert(str);
//                    str = "";
//                }
//            }else str += s[i];
//        }
//        printf("%d\n", d.size());
//
//    }
//
//    return 0;
//}
//2072

//int main()
//{
//    int n, a, b;
//    while (scanf("%d%d%d", &n, &a, &b) == 3)
//    {
//        int as[100] = { 0 }, bs[100] = { 0 };
//        int i = n;
//        while (i--){
//            as[i] = a % 10; bs[i] = b % 10;
//            a /= 10; b /= 10;
//        }
//        stack<int> s;
//        while (!s.empty()) s.pop();
//        int ia = 0, ib = 0;
//        int flag = 0;
//        int k[1000] = { 0 }, ki = 1;
//        while (ib < n){
//            if (as[ia] == bs[ib]){
//                ia++; ib++;
//                k[ki] = 1;
//                ki++;
//                k[ki] = -1;
//                ki++;
//            }
//            else if (!s.empty() && s.top() == bs[ib]){
//                s.pop();
//                ib++;
//                k[ki] = -1;
//                ki++;
//            }
//            else if (ia <= n){
//                s.push(as[ia]);
//                ia++;
//                k[ki] = 1;
//                ki++;
//            }
//            else {
//                printf("No.\nFINISH\n");
//                flag = 1;
//                break;
//            }
//        }
//        if (flag == 0){
//            printf("Yes.\n");
//            for (i = 1; i < ki; i++){
//                if (k[i] == 1)printf("in\n");
//                else printf("out\n");
//            }
//            printf("FINISH\n");
//        }
//    }
//    return 0;
//}
//int main()
//{
//    

//    int num = 0;
//    scanf("%d", &num);
//    while (num--){
//        ll a[4] = { 0 };
//        ll t=0;
//        int flag = 0;
//        scanf("%I64d%I64d%I64d", &a[1], &a[2], &t);
//        if (a[1] == t || a[2] == t){ printf("Yes\n"); continue; }
//        while (1){
//            a[3] = a[1] + a[2];
//            if (a[3] == t){
//                flag = 1;
//                break;
//            }
//            if (a[3] > t)break;
//            a[1] = a[2]; a[2] = a[3];
//        }
//        if (flag)printf("Yes\n");
//        else printf("No\n");
//    }
//
//    return 0;
//}

//int main()
//{
//    int m;
//    while (scanf("%d", &m)==1)
//    {
//        int t = 1;
//        int step = 0;
//        do
//        {
//            if (t<= m)t = 2 * t;
//            else t = 2 * (t - m) - 1;
//            step += 1;
//        } while (t != 1);
//        printf("%d\n", step);
//    }
//}

//int main()
//{
//    int a, b,i;
//    while (scanf("%d%d", &a, &b) == 2)
//    {
//        int M1 = a, M2 = b;
//        int R1 = 00, R2 = 0 ,R3 = 0;
//        char zl[250];
//        scanf("%s",zl);
//        int len = strlen(zl);
//        for (i = 0; i <= len - 1; i++){
//            if (zl[i] == 'A')R1 = M1;
//            else if(zl[i] == 'B')R2 = M2;
//            else if(zl[i] == 'C')M1 = R3;
//            else if(zl[i] == 'D')M2 = R3;
//            else if(zl[i] == 'E')R3 = R1 + R2;
//            else if(zl[i] == 'F')R3 = R1 - R2;
//        }
//        printf("%d,%d\n", M1, M2);
//    }
//    return 0;
//}

//int main()
//{
//    int a0, a1, a2, a3, a4, a6, a5, a7;
//    while(sf("%d", &a0) == 1&& a0!=-1)
//    {
//        sf("%d%d%d%d%d%d%d", &a1, &a2, &a3, &a4, &a5, &a6, &a7);
//        int sum1 = a0 + a2 + a5 + a7;
//        int sum2 = a1 + a3 + a4 + a6;
//        if (sum1 == sum2)pf("All the seeds can be cleared away!\n");
//        else pf("Sorry,it can't be cleared away!\n");
//    }
//    return 0;
//}

//int main()
//{
//    int n;
//    sf("%d", &n);
//    while (n--){
//        int a1, b1, a2, b2, a3, b3;
//        sf("%d%d%d%d%d%d", &a1, &a2, &a3, &b1, &b2, &b3);
//        if (a1 > b1)printf("First\n");
//        else if (a1 < b1)printf("Second\n");
//        else if (a1 == b1){
//            if (a2 > b2)printf("First\n");
//            else if (a2 < b2)printf("Second\n");
//            else if (a2 == b2){
//                if (a3>b3)printf("First\n");
//                else if (a3 < b3)printf("Second\n");
//                else if (a3 == b3)printf("Same\n");
//            }
//        }
//    }
//    return 0;
//}

//int main()
//{
//    ll i, a[250] = { 0 };
//    a[1] = 1; a[2] = 2;
//    for (i = 3; i <= 210; i++)a[i] = a[i - 1] + a[i - 2];
//    int n;
//    sf("%d", &n);
//    while (n--)
//    {
//        char s[250];
//        sf("%s", s);
//        int len = strlen(s);
//        pf("%I64d\n", a[len]);
//    }
//    return 0;
//}

//int main()
//{
//    char s[10000];
//    while (scanf("%s", s) == 1)
//    {
//        int sum = 0,i;
//        int len = strlen(s);
//        for (i = 0; i <= len - 1; i++){
//            if (s[i] == '(')sum += 1;
//            else if (s[i] == ')')sum -= 1;
//            else if (s[i] == 'B')break;
//        }
//        printf("%d\n", sum);
//    }
//    return 0;
//}

//int main()
//{
//    ll a[60],i,n;
//    a[1] = 3; a[2] = 6; a[3] = 6;
//    for (i = 4; i <= 53; i++)a[i] = 2 * a[i - 2] + a[i - 1];
//    while (scanf("%I64d", &n) == 1)printf("%I64d\n", a[n]);
//    return 0;
//}

//int main()
//{
//    int temp = 1,k,i,n;
//    ll fm = 2, fz[25];
//    double a[25];
//    a[1] = 0; a[2] = 0.5;
//    fz[1] = 0; fz[2] = 1;
//    for (i = 3; i <= 21; i++){
//        fz[i] = (i - 1)*(fz[i - 1] + fz[i - 2]);
//        temp += 1;
//        fm *= temp + 1;
//        a[i] = fz[i]/ (double)fm;
//    }
//    scanf("%d", &n);
//    while (n --)scanf("%d", &k), pf("%.2lf%%\n", a[k]*100);
//    return 0;
//}

//int main()
//{
//    ll n, m, a;
//    while (sf("%I64d%I64d%I64d",&n,&m,&a)==3)
//    {
//        ll sum = (n / a + (n%a + a - 1) / a)*(m / a + (m%a + a - 1) / a);
//        pf("%I64d", sum);
//    }
//    return 0;
//}
//

//int main()
//{
//    int n;
//    while (scanf("%d", &n) == 1 && n){
//        int i,t, max = 0;
//        for (i = 1; i <= n; i++){
//            sf("%d", &t);
//            if (t > max)max = t;
//        }
//        printf("%d\n", max);
//    }
//}

#define eps 1e-8
#define MAXN 1000
struct point { double x, y; }pt[MAXN];
#define _sign(x)((x)>eps?1:((x)<-eps?2:0))
//
//double xmult(point p1, point p2, point p0) 
//{
//    return (p1.x - p0.x)*(p2.y - p0.y) - (p2.x - p0.x)*(p1.y - p0.y);
//}
//int is_convex(int n, point* p) 
//{ 
//    int i, s[3] = { 1, 1, 1 }; 
//    for (i = 0; i<n&&s[1] | s[2]; i++) s[_sign(xmult(p[(i + 1) % n], p[(i + 2) % n], p[i]))] = 0;
//    return s[1] | s[2]; 
//}
//int main()
//{
//    int n,i;
//    point p[100];
//    while (scanf("%d" , &n) == 1 && n){
//        for (i = 1; i <= n ; i++)scanf("%lf%lf", &p[i].x, &p[i].y);
//        if (is_convex(n, p))printf("convex\n");
//        else printf("concave\n");
//    }
//    return 0;
//}

//int main()
//{
//    int n, u;
//    while (scanf("%d%d", &n,  &u) == 2)printf("%.2lf\n", (double)1 / n);
//    return 0;
//}

//int calc(int n)
//{
//    int s = 1;
//    if (n == 0)return 0;
//    for (int i = 1; i <= n; i++)s *= i;
//    return s;
//}
//int main()
//{
//    ll i;
//    int num[10] = { 0 };
//    num[1] = 1;
//    for (i = 1; i <=1000000; i++){
//        if ((calc(num[1]) + calc(num[2]) + calc(num[3]) + calc(num[4]) + calc(num[5])) == i) printf("%d\n", i);
//        num[1] += 1;
//        if (num[1] == 10)num[1] = 0, num[2] += 1;
//        if (num[2] == 10)num[2] = 0, num[3] += 1;
//        if (num[3] == 10)num[3] = 0, num[4] += 1;
//        if (num[4] == 10)num[4] = 0, num[5] += 1;
//        if (num[5] == 10)num[5] = 0, num[6] += 1;
//    }
//    return 0;
//}
//
//int main()
//{
//    printf("1\n2\n145\n40585\n");
//    return 0;
//}

//int main()
//{
//    char a[10000]; int j;
//    while (gets(a)){
//        int len = strlen(a);
//        int i = 0;
//        while (a[i] != '\0'){
//            if (a[i] == ' '){
//                for (j = i; j <= len - 2; j++)a[j] = a[j + 1];
//                a[len - 1] = '\0';
//                len--;
//            }
//            if (a[i] == ' ')i--;
//            i++;
//        }
//        for (i = 2; i <= len - 1; i += 3){
//            printf("%c", a[i]);
//            a[i] = ' ';
//        }
//        for (i = 1; i <= len-1; i += 2){
//            if ((i + 1) % 3 != 0)printf("%c", a[i]), a[i] = ' ';
//        }
//        for (i = 0; i <= len - 1; i++)if (a[i] != ' ')printf("%c", a[i]);
//        printf("\n");
//    }
//    return 0;
//}

//int main()
//{
//    int i,a[50];
//    a[1] = 2; a[2] = 3; a[3] = 5;
//    for (i = 4; i <= 31; i++)a[i] = a[i - 1] + 2 * a[i - 2];
//    int n,k;
//    scanf("%d", &n);
//    while (n--)scanf("%d", &k), printf("%d\n", a[k]);
//    return 0;
//}

//int main()
//{
//    int n;
//    scanf("%d", &n);
//    while (n--)
//    {
//        int k,i,j;
//        scanf("%d", &k);
//        for (i = 1; i <= 3 * k; i++){
//            for (j = 1; j <= k; j++)printf("HDU");
//            printf("\n");
//        }
//    }
//}

//int main()
//{
//    int s[30][30] = { 0 };
//    int a[30] = { 0 };
//    int i,j;
//    s[1][1] = 1;
//    for (i = 1; i <= 25; i++)s[1][i] = 1;
//    for (i = 2; i <= 25; i++){
//        for (j = 2; j <= 25; j++)s[j][i] = s[j - 1][i - 1] + s[j][i - 1];
//    }
//    for (i = 1; i <= 25; i++)for (j = 1; j <= 25; j++)a[i] += j * s[j][i];
//    int n;
//    scanf("%d", &n);
//    while (n--)
//    {
//        int k;
//        scanf("%d", &k);
//        printf("%d\n", a[k]);
//    }
//    return 0;
//}

//int gcd(int a, int b)
//{
//    if (0 == b)
//        return a;
//    if (a<b)
//        swap(a, b);
//    return gcd(b, a%b);
//}
//int main()
//{
//    int n, a, b, c;
//    sf("%d", &n);
//    while (n--)
//    {
//        scanf("%d%d", &a, &b);
//        a = a / b;
//        int i = 1;
//        while (i++)
//        if (gcd(a, i) == 1)
//        {
//            c = b*i;
//            break;
//        }
//        printf("%d\n", c);
//    }
//    return 0;
//}

//double calc(int a, int b, int c, int d)
//{
//    return sqrt((double)(a - c)*(a - c) + (b - d)*(b - d));
//}
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    while (n--)
//    {
//        double a, b, c, d;
//        scanf("%lf%lf%lf%lf", &a, &b, &c, &d);
//        printf("%.1lf\n", calc(a, b, c, d));
//    }
//    return 0;
//}

//int main()
//{
//    int k,n,m;
//    scanf("%d", &k);
//    while (k--)
//    {
//        sf("%d%d", &m, &n);
//        printf("%d\n", (m + 1)*m / 2 * (n + 1)*n / 2);
//    }
//    return 0;
//}

//int main()
//{
//    int n;
//    while (scanf("%d", &n) == 1)
//    {
//        if (n == 2){
//            printf("NO\n"); continue;
//        }
//        if (n % 2 == 0)printf("YES\n");
//        else printf("NO\n");
//
//    }
//    return 0;
//}
//int main()
//{
//    char a[10000];
//    int i;
//    while (1)
//    {
//        gets(a);
//        if (a[0] == '#')break;
//        int len = strlen(a);
//        for (i = 0; i <= len-1; i++){
//            if (a[i] == ' ')printf("%%20");
//            else if (a[i] == '!')printf("%%21");
//            else if (a[i] == '$')printf("%%24");
//            else if (a[i] == '%')printf("%%25");
//            else if (a[i] == '(')printf("%%28");
//            else if (a[i] == ')')printf("%%29");
//            else if (a[i] == '*')printf("%%2a");
//            else printf("%c", a[i]);
//        }
//        printf("\n");
//    }
//    return 0;
//}

//int main()
//{
//    char a[1000];
//    int i;
//    while (1)
//    {
//        gets(a);
//        if (a[0] == '#')break;
//        int len = strlen(a);
//        int sum = 0;
//        for (i = 0; i <= len - 1; i++){
//            if (a[i] != ' ')sum += (i + 1)*((int)a[i] - 64);
//        }
//        printf("%d\n", sum);
//    }
//    return 0;
//}

//ll a[1000000] = { 0 };
//int main()
//{
//
//    int i;
//    a[1] = 1; a[2] = 7; a[0] = 0;
//    for (i = 3; i <=4018; i++){
//        a[i] = (a[i - 2] + 3 * i*(i - 1) + 1) % 2009;
//        //if (a[i - 2] == a[1] && a[i - 1] == a[2] && a[i] == a[3] && i!=3){ printf("%d", i); break; }
//    }
//    ll n;
//    while (scanf("%I64d", &n) == 1 && n){
//        printf("%I64d\n", a[n%4018]);
//    }
//    return 0;
//}

//int main()
//{
//    int n,i;
//    scanf("%d", &n);
//    while (n--){
//        char a[1000] = "\0";
//        scanf("%s", a);
//        int len = strlen(a) - 1;
//        _strlwr(a);
//        for (i = 0; i <=len; i++){
//            if (a[i] == 'a')a[i] = 'A';
//            else if (a[i] == 'e')a[i] = 'E';
//            else if (a[i] == 'i')a[i] = 'I';
//            else if (a[i] == 'o')a[i] = 'O';
//            else if (a[i] == 'u')a[i] = 'U';
//        }
//        printf("%s\n", a);
//    }
//    return 0;
//}

//#include <stdio.h>
//#include <math.h>
//double a1, a2, a3, a4;
//double f(double x)
//{
//    return (a1*x*x*x + a2*x*x + a3*x + a4);
//}
//int main()
//{
//    double a, b, t=1, c;
//
//    scanf("%lf%lf%lf%lf", &a1, &a2, &a3, &a4);
//    scanf("%lf%lf", &a, &b);
//    do {
//        if ((f(a)*f(b))<0)
//        {
//            if (f((a + b) / 2) == 0)
//            {
//                printf("%.2lf", (a + b) / 2);
//            }
//            else
//            {
//                //c = (f(a) + f(b)) / 2;
//                ////if (c*f(a)>0)
//                //{
//                //    a = c;
//                //}
//                //else
//                //{
//                //    b = c;
//                //}
//                //
//                c = (a + b) / 2;
//                if (f(c)*f(a) > 0)a = c;
//                else if (f(c)*f(b) > 0)b = c;
//                t = fabs(a - b);
//            }
//        }
//    } while (t>0.01);
//    printf("%.2f", (a + b) / 2);
//    getchar();
//    return 0;
//}

//int main()
//{
//    int n, m,j,i;
//    while (scanf("%d%d", &n, &m) == 2){
//        if (n == 0 && m == 0)break;
//        int a[30000] = { 0 };
//        int b[30000] = { 0 };
//        for (i = 1; i <= n; i++)scanf("%d", &a[i]);
//        for (i = 1; i <= m; i++)scanf("%d", &b[i]);
//        sort(a + 1, a + n + 1);
//        sort(b + 1, b + m + 1);
//        int sum = 0;
//        int t = 1;
//        for (i = 1; i <= m; i++){
//            /*for (j = t; j <= n; j++){
//                if (a[n] == 0)break;
//                if (b[i] >= a[j] && a[j]){
//                    a[j] = 0;
//                    sum += b[i];
//                    b[i] = 0;
//                    t++;
//                    continue;
//                }
//            }*/
//            if (b[i] >= a[t]){
//                sum += b[i];
//                t++;
//                if (t == n + 1)break;
//            }
//        }
//        if (t==n+1)printf("%d\n", sum);
//        else printf("Loowater is doomed!\n");
//    }
//    return 0;
//} //UVa11292

//int main()
//{
//    int n,i;
//    scanf("%d", &n);
//    while (n--)
//    {
//        int t;
//        char a[] = "0ZJUTACM";
//        scanf("%d", &t);
//        int wz = 2l;
//        while (t--)
//        {
//            int x, y;
//            scanf("%d%d", &x, &y);
//            char temp = a[x];
//            a[x] = a[y];
//            a[y] = temp;
//            /*if (x == wz) wz = y;
//            else if (y == wz)wz = x;*/
//        }
//        for (i = 1; i <= strlen(a); i++)if (a[i] == 'J')break;
//        printf("%d\n", i);
//        //printf("%d\n", wz);
//    }
//    return 0;
//}

//int main()
//{
//    int n;
//    scanf("%d", &n);
//    while (n--){
//        int k,i;
//        int a[1000] = { 0 };
//        scanf("%d", &k);
//        for (i = 1; i <= k; i++)scanf("%d", &a[i]);
//        sort(a+1,a+k+1);
//        printf("%d\n", a[2]);
//    }
//    return 0;
//}

//int main()
//{
//    int n,i;
//    scanf("%d", &n);
//    while (n--)
//    {
//        char a[100] = "\0";
//        scanf("%s", a);
//        int len = strlen(a);
//        for (i = 1; i <= len - 1; i+=2){
//            char t = a[i];
//            a[i] = a[i - 1];
//            a[i - 1] = t;
//        }
//        printf("%s\n", a);
//    }
//    return 0;
//}

//int main()
//{
//    int i,a[100] = { 00 };
//    a[1] = 3; a[2] = 7;
//    for (i = 3; i <= 30; i++)a[i] = 2 * a[i - 1] + a[i - 2];
//    int n;
//    scanf("%d", &n);
//    while (n--)
//    {
//        int k;
//        scanf("%d", &k);
//        printf("%d\n", a[k]);
//    }
//    return 0;
//}

//int main()
//{
//    int i,n;
//    scanf("%d", &n);
//    getchar();
//    while (n--)
//    {
//        int k;
//        scanf("%d", &k);
//        int a = 1, b = k;
//        int temp = k;
//        while (k--){
//            for (i = 1; i <= temp; i++){
//                if (i == a)printf("X");
//                else if (i == b)printf("X");
//                else printf(" ");
//                if (a >= b && i == a)break;
//                else if (b >= a && i == b)break;
//            }
//            a++; b--;
//            printf("\n");
//        }
//        printf("\n");
//    }
//    return 0;
//}

//int main()
//{
//    int n,i,j,k;
//    scanf("%d", &n);
//    while (n--)
//    {
//        int a, b,sum=0;
//        scanf("%d%d", &a, &b);
//        for (i = 0; i <= b / 5; i++){
//            for (j = 0; j <= (b - 5 * i) / 2; j++){
//                for (k = 0; k <= (b - 5 * i - 2 * j);k++)
//                if ((5 * i + 2 * j + k) == b && (i+j+k)==a)sum += 1;
//            }
//        }
//        printf("%d\n", sum);
//    }
//    return 0;
//}

//int main()
//{
//    int n;
//    while (scanf("%d", &n) == 1 && n)
//    {
//        int s = 0;
//        while (n--)
//        {
//            int t;
//            scanf("%d", &t);
//            s += (int)t / 100;
//            s += (int)(t % 100) / 50;
//            s += (int)((t % 50) / 10);
//            s += (int)(( t% 10) / 5);
//            s += (int)(t % 5) / 2;
//            s += (t % 5) % 2;
//        }
//        printf("%d\n", s);
//    }
//    return 0;    
//}

//int main()
//{
//    int n,i;
//    while (scanf("%d", &n) == 1){
//        if (n == 0){
//            printf("0\n");
//            continue;
//        }
//        int a[10000] = { 0 };
//        int t=0;
//        while (n != 0){
//            a[t] = n % 2;
//            t++;
//            n /= 2;
//        }
//        for (i = t-1; i >= 0; i--)printf("%d", a[i]);
//        printf("\n");
//    }
//    return 0;
//}

//int main()
//{
//    int a = -2;
//    printf("%d位于%d", a, &a);
//    getchar();
//}

//int main()
//{
//    char a[9999];
//    int i,j;
//    while (scanf("%s", &a) == 1){
//        int b[10000] = { 0 };
//        int len = strlen(a);
//        string t="";
//        int st = 0,ep=0;
//        for (i = 0; i <= len; i++){
//            if (a[i] == '5' && (a[i + 1] != '5' ) || a[i] == '\0'){
//                if (i != st){
//                    for (j = st; j <= i - 1; j++){
//                        if(a[j]!='5')t += a[j];
//                    }
//                    if (t == "")continue;
//                    stringstream ss;
//                    ss << t;
//                    
//                    ss >> b[ep];
//                    t = "";
//                    ep += 1;
//                }
//                st = i + 1;
//            }
//        }
//        sort(b, b + ep);
//        int flag = 0;
//        for (i = 0; i <= ep - 1; i++){
//            if (flag)printf(" %d", b[i]);
//            else{
//                printf("%d", b[i]);
//                flag = 1;
//            }
//        }
//        printf("\n");
//    }
//    return 0;
//}

//int a[1000100], dp;
//int main()
//{
//    int i, n, t, j, u, v, s = 1, m, x;
//    scanf("%d", &t);
//    while (t--)
//    {
//        scanf("%d", &n);
//        for (i = 1; i <= n; i++) scanf("%d", &a[i]);
//        printf("Case %d:\n", s++);
//        dp = m = a[1];
//        u = v = x = 1;
//        for (i = 2; i <= n; i++)
//        {
//            if (dp >= 0) dp += a[i];
//            else dp = a[i], x = i;
//            if (m<dp) v = i, m = dp, u = x;
//        }
//        printf("%d %d %d\n", m, u, v);
//        if (t != 0) printf("\n");
//    }
//    return 0;
//}

//int main()
//{
//    char b, a[1100];
//    while (scanf("%c%s", &b, a)==2)
//    {
//        getchar();
//        int len = strlen(a);
//        int i,sum = 0;
//        for (i = 0; i <= len - 1; i++){
//            if (towlower(a[i]) == towlower(b) || towupper(a[i]) == towupper(b) )sum += 1;
//        }
//        printf("%.5lf\n", (double)sum / len);
//        memset(a, 0, sizeof(a));
//    }
//    return 0;
//}

//int main()
//{
//    double n, m;
//    while (scanf("%lf%lf", &n, &m) == 2){
//        int sum = 0;
//        int i = 1;
//        while (n >= 0.000001)
//        {
//            int k=i;
//            while (k--){
//                n -= m;
//                sum += 1;
//                if (n <= 0.000001)break;
//            }
//            if (n <= 0.000001)break;
//            sum += 1;
//            i++;
//        }
//        printf("%d\n", sum);
//    }
//    return 0;
//}

//int main()
//{
//    int n;
//    while (scanf("%d", &n) == 1){
//        int i, j, k;
//        for (i = 1; i <= sqrt(n / 3.0); i++){
//            for (j = 1; j <= sqrt((n*1.0 - i*i) / 2); j++){
//                for (k = sqrt(n*1.0 - i*i - j*j); k <= sqrt(n*1.0 - i*i - j*j) + 1; k++){
//                    if ((i*i + j*j + k*k) == n) {
//                        printf("%d %d %d\n", i, j, k);
//                        break;
//                    }
//                }
//                if ((i*i + j*j + k*k) == n)break;
//            }
//            if ((i*i + j*j + k*k) == n)break;
//        }
//    }
//    return 0;
//}

//int main()
//{
//    int n,i,l;
//    scanf("%d", &n);
//    while (n--)
//    {
//        int k,d;
//        scanf("%d%d", &k,&d);
//        if (k > d){
//            int t = k;
//            k = d;
//            d = t;
//        }
//        int sum = 0;
//        int num = 0;
//        for (l = k; l <= d; l++){
//            for (i = 1; i <= sqrt(l); i++){
//                if (l%i == 0) {
//                    sum += i;
//                    if (l / i < l && i != sqrt(l))sum += l / i;
//                }
//            }
//            if (sum == l)num += 1;
//            sum = 0;
//        }
//        
//        printf("%d\n", num);
//    }
//    return 0;
//}

//int main()
//{
//    char s;
//    int flag = 0,n;
//    while (scanf("%c%d", &s,&n) == 2){
//        getchar();
//        if (s == '@')break;
//        if (flag==1)printf("\n");
//        else flag=1;
//        int i,j;
//        int fa, fb;
//        fa = fb = n;
//        for (i = 1; i <= n - 1; i++){
//            for (j = 1; j <= fb; j++){
//                if (j == fa){
//                    printf("%c", s);
//                }
//                else if (j == fb){
//                    printf("%c", s);
//                }
//                else printf(" ");
//            }
//            fb++; fa--;
//            printf("\n");
//        }
//        for (i = 1; i <= (2 * n - 1); i++)printf("%c", s);
//        printf("\n");
//    }
//    return 0;
//}

//int main()
//{
//    int a[4];
//    while (scanf("%d%d%d", &a[1], &a[2], &a[3]) == 3 && (a[1] + a[2] + a[3])){
//        sort(a + 1, a + 4);
//        if ((a[1] * a[1] + a[2] * a[2]) == a[3] * a[3])printf("right\n");
//        else printf("wrong\n");
//    }
//    return 0;
//}

//int main()
//{
//    int n;
//    scanf("%d", &n);
//    while (n--){
//        int y, m, d;
//        scanf("%d-%d-%d", &y, &m, &d);
//        if (m == 2 && d == 29){
//            printf("-1\n");
//            continue;
//        }
//        int i;
//        int sum=0;
//        for (i = 1; i <=17; i++){
//            int t = y + i;
//            if ((t % 4 == 0 && t % 100 != 0) || t % 400 == 0)sum += 366;
//            else sum += 365;
//        }
//        if (((y % 4 == 0 && y % 100 != 0) || y % 400 == 0) && m <= 2 && d <= 29) sum += 366;
//        else {
//            //sum += 365;
//            y = y + 18;
//            if (((y % 4 == 0 && y % 100 != 0) || y % 400 == 0) && m > 2 ) sum += 366;
//            else sum += 365;
//        }
//        printf("%d\n", sum);
//    }
//    return 0;
//}

//int main()
//{
//    char a[1001];
//    int n,i;
//    while (scanf("%s%d",a, &n) == 2)
//    {
//        int ynum = 0;
//        int len = strlen(a);
//        for (i = 0; i <= len - 1;i++){
//            ynum = ynum * 10 + (a[i] - '0');
//            ynum %= n;
//        }
//        printf("%d\n", ynum);
//    }
//    return 0;
//}

//int main()
//{
//    double a, b, c, m, n, l, v;
//    while (scanf("%lf%lf%lf%lf%lf%lf", &a, &c, &b, &n, &l, &m) ==6)
//    {
//        v = (double)sqrt((4.0*a*a*b*b*c*c - a*a*(b*b + c*c - m*m)*(b*b + c*c - m*m) - b*b*(c*c + a*a - n*n)*(c*c + a*a - n*n) - c*c*(a*a + b*b - l*l)*(a*a + b*b - l*l) + (a*a + b*b - l*l)*(b*b + c*c - m*m)*(c*c + a*a - n*n))) / 12.0;
//        printf("%.4lf\n", v);
//    }
//    return 0;
//}

//set<int> a;
//int main()
//{
//    int n, m;
//    while (scanf("%d%d", &n, &m) == 2){
//        int t,i;
//        for (i = 1; i <= n; i++){
//            scanf("%d", &t);
//            a.insert(t);
//        }
//        for (i = 1; i <= m; i++){
//            scanf("%d", &t);
//            a.insert(t);
//        }
//        int flag = 0;
//        for (set<int>::iterator it = a.begin(); it != a.end(); ++it){
//            if (flag)printf(" %d", *it);
//            else {
//                printf("%d", *it);
//                flag = 1;
//            }
//        }
//        printf("\n");
//        a.clear();
//    }
//    return 0;
//}

//void move(int n, char a, char b, char c)
//{
//    if (n == 1)
//        printf("\t%c->%c\n", a, c);    //当n只有1个的时候直接从a移动到c
//    else
//    {
//        move(n - 1, a, c, b);            //第n-1个要从a通过c移动到b
//        printf("\t%c->%c\n", a, c);
//        move(n - 1, b, a, c);            //n-1个移动过来之后b变开始盘，b通过a移动到c，这边很难理解
//    }
//}
//
//int main()
//{
//    int n;
//    printf("请输入要移动的块数：");
//    scanf("%d", &n);
//    move(n, 'a', 'b', 'c');
//    scanf("%d", &n);
//    return 0;
//}

//ll a[100] = { 0 };
//ll b[100] = { 0 };
//
//ll kmin(int a, int c)
//{
//    int k = b[a], i;
//    for (i = a; i <= c; i++){
//        if (b[i] < k)k = b[i];
//    }
//    return k;
//}
//void dp()
//{
//    int i,j;
//
//    for (i = 3; i <= 67; i++){
//        for (j = 1; j <= i; j++){
//            b[j] = 2 * a[i - j] + pow(2, j) - 1;
//            if (b[j] == 0)b[j] = 9999999;
//        }
//        a[i] = kmin(1,i);
//    }
//}
//
//int main()
//{
//    a[1] = 1; a[2] = 3;
//    dp();
//    a[63] = 17409;
//    a[64] = 18433;
//    int n;
//    while (scanf("%d", &n) == 1)printf("%I64d\n", a[n]);
//}

//char a[50];
//int judge()
//{
//    int len = strlen(a);
//    int i;
//    for (i = 0; i <= len - 1; i++){
//        if (!isdigit(a[i]) && a[i] != '.') return 0;
//    }
//    int g, b, c, d;
//    char e;
//    return 4 == sscanf(a, "%3d.%3d.%3d.%3d%c", &g, &b, &c, &d, &e) && g < 256 & b < 256 && c < 256 && d < 256;
//}
//int main()
//{
//    while (gets(a)){
//        int k = judge();
//        if (k)printf("YES\n");
//        else printf("NO\n");
//    }
//    return 0;
//}

//int main()
//{
//    ll a[99] = { 0 };
//    a[0] = 1;
//    a[2] = 3;
//    for (int i = 4; i <= 64; i += 2)a[i] = 4 * a[i - 2] - a[i - 4];
//    
//    int n;
//    while (scanf("%d", &n) == 1 && n != -1){
//        printf("%I64d\n", a[n]);
//    }
//    return 0;
//}

//int main()
//{
//    int n;
//    scanf("%d", &n);
//    while (n--){
//        int t;
//        scanf("%d", &t);
//        printf("%d\n", t*(t - 1) * 3 + 2);
//    }
//    return 0;
//}

//
//int main()
//{
//    int n,i;
//    while (scanf("%d", &n) == 1){
//        int sum = 0;
//        for (int i = 0; 3 * i <= n; ++i)
//            sum += (n - 3 * i) / 2 + 1;
//        printf("%d\n", sum);
//    }
//    return 0;
//}
//

//int main()
//{
//    ll t;
//    scanf("%d", &t);
//    while (t--){
//        ll n, m;
//        scanf("%I64d%I64d", &n, &m);
//        ll i, j, k;
//        ll s[1000] = { 0 };
//        ll p[1000] = { 0 };
//        ll q[1000] = { 0 };
//        ll min[1000] = { 0 };
//        for (i = 1; i <= n; i++)sf("%I64d%I64d", &s[i], &p[i]);
//        for (i = 1; i <= m; i++)sf("%I64d", &q[i]);
//        ll kmin = 99999999;
//        /*for (i = 2; i <= n; i++)if (kmin > (s[i] * p[i]))kmin = s[i] * p[i];*/
//        for (i = 1; i <= m; i++)
//        {
//            for (j = 1; j <= n; j++){
//                if (q[i] <= s[j] && q[i] >= s[j - 1])break;
//            }
//            /*if (j > n){
//                if ((q[i] * p[j - 1]) > kmin)printf("%d", kmin);
//                else printf("%d\n", q[i] * p[j - 1]);
//            }
//            else{
//                if ((q[i] * p[j - 1]) <= (s[j] * p[j])){
//                    if ((q[i] * p[j - 1]) > kmin)printf("%d", kmin);
//                    else printf("%d\n", q[i] * p[j - 1]);
//                }
//                else {
//                    if ((s[j] * p[j]) > kmin)printf("%d", kmin);
//                    else printf("%d\n", (s[j] * p[j]));
//                }
//            }*/
//            kmin = q[i] * p[j - 1];
//            for (k = 0;; k++){
//                if (p[j + k] == 0)break;
//                ll t = p[j + k] * s[j + k];
//                if (t <= kmin)kmin = t;
//            }
//            printf("%I64d\n", kmin);
//        }
//    }
//    return 0;
//}
//

//int main()
//{
//    int i;
//    int N;
//    int n, m;
//    int a, b;
//    int count, x;
//    scanf("%d", &N);
//    for (i = 0; i<N; i++)
//    {
//        x = 1;
//        while (scanf("%d %d", &n, &m)==2 && n>0)
//        {
//            count = 0;
//            for (a = 1; a<n - 1; a++)
//            for (b = a + 1; b<n; b++)
//            if ((a*a + b*b + m) % (a*b) == 0)
//                count++;
//            printf("Case %d: %d\n", x++, count);
//        }
//        if (i != N - 1)
//            printf("\n");
//    }
//    return 0;
//}

//int main()
//{
//    int n;
//    scanf("%d", &n);
//    int f = 0;
//    while (n--){
//        int k,i;
//        int sum[10000] = { 0 };
//        while (1){
//            char a[10000] = "\0";
//            scanf("%s", a);
//            int len = strlen(a);
//            for (i = len - 1; i >= 0; i--){
//                sum[len - i] += a[i] - '0';
//                if (sum[len - i] >= 10){
//                    sum[len - i] %= 10;
//                    sum[len - i + 1] += 1;
//                }
//            }
//            if (a[0] == '0'){
//                int flag = 0;
//                for (i = 9999; i >= 1; i--){
//                    if (flag == 0){
//                        if (sum[i] != 0){
//                            flag = 1;
//                            printf("%d", sum[i]);
//                        }
//                    }
//                    else printf("%d", sum[i]);
//                }
//                if (flag == 0)printf("0");
//                if(n==0)printf("\n");
//                else printf("\n\n");
//                break;
//            }
//        }
//        
//        /*int flag = 0;
//        for (i = 9999; i >= 1; i--){
//            if (flag==0){
//                if (sum[i] != 0){
//                    flag = 1;
//                    printf("%d", sum[i]);
//                }
//            }
//            else printf("%d", sum[i]);
//        }
//        printf("\n");*/
//    }
//    return 0;
//}

//int main()
//{
//    double n;
//    while (scanf("%lf", &n) == 1 && n){
//        double a = 0, fm = 2, sum = 0;
//        while (a <= n-eps){
//            a += 1 / fm;
//            fm++;
//            sum++;
//        }
//        printf("%d card(s)\n", (int)sum);
//    }
//    return 0;
//}

//int main() {
//    int n;
//    scanf("%d", &n);
//    while (n--) {
//        int N = 0;
//        scanf("%d", &N);
//        double x = N*log10(N*1.);
//        double x1 = x - (long long)x;
//        double x2 = pow(10., x1);
//        printf("%d\n", (int)x2);
//    }
//    return 0;
//}

//int main()
//{
//    int n;
//    scanf("%d", &n);
//    getchar();
//    while (n--)
//    {
//        char a[9999];
//        gets(a);
//        int len = strlen(a);
//        int st = 0,i,j;
//        a[len] = ' ';
//        len++; int flag = 0;
//        for (i = 0; i <= len - 1; i++){
//            if (a[i] == ' ' || a[i]=='\0'){
//                if (flag == 1)printf(" ");
//                else flag = 1;
//                for (j = i - 1; j >= st; j--){
//                    printf("%c", a[j]);
//                }
//                st = i + 1;
//            }
//        }
//        printf("\n");
//    }
//    return 0;
//}

//int main()
//{
//    int n = 12;
//    double sum=0;
//    while (n--){
//        double k;
//        scanf("%lf", &k);
//        sum += k;
//    }
//    printf("$%.2lf\n", sum / 12);
//}

//int main()
//{
//    int n;
//    scanf("%d", &n);
//    while (n--)
//    {
//        int z;
//        scanf("%d", &z);
//        int a1, b1, c1;
//        int a2, b2, c2;
//        scanf("%d%d%d", &a1, &b1, &c1);
//        z--;
//        double max = 0;
//        while (z--){
//            scanf("%d%d%d", &a2, &b2, &c2);
//            double dis = (double)(b2 - b1)*(b2 - b1) + (double)(c2 - c1)*(c2 - c1);
//            double t = sqrt(dis) / int((double)(a2 - a1));
//            if (t > max)max = t;
//            a1 = a2; b1 = b2; c1 = c2;
//        }
//        printf("%.10lf\n", max);
//    }
//    return 0;
//}

//int main()
//{
//    char a[99];
//    char b[99];
//    char c[99];
//    char d[99];
//    while (sf("%s", &a) == 1)
//    {
//        scanf("%s", &b);
//        int i;
//        int lena = strlen(a);
//        int lenb = strlen(b);
//        int flag = 0;
//        for (i = 0; i <= lena - 1; i++){
//            if (flag)printf("%c", a[i]);
//            if (a[i] == '_')flag = 1;
//        }
//        printf("_small_");
//        flag = 0;
//        for (i = 0; i <= lenb - 1; i++){
//            if (flag)printf("%c", b[i]);
//            if (b[i] == '_')flag = 1;
//        }
//        printf("\n");
//    }
//    return 0;
//}

int main()
{
    char ot[50][50] = { "00000", "00001", "00010", "00011", "00100", "00101", "00110", "00111", "01000", "01001",
        "01010", "01011", "01100", "01101", "01110", "01111",
        "10000", "10001", "10010", "10011", "10100", "10101", "10110", "10111", "11000",
        "11001", "11010", "11011", "11100", "11101", "11110", "11111" };
    int sign;
    while (scanf("%d", &sign) == 1 ){
        getchar();
        if (sign){
            char a[20];
            gets(a);
            int f, b;
            if (a[0] == 'A' && a[1] == 'D' && a[2] == 'D'){
                if (isdigit(a[6])){
                    f = (a[5] - '0') * 10 + (a[6] - '0');
                    if (isdigit(a[10])){
                        b = (a[9] - '0') * 10 + (a[10] - '0');
                    }
                    else b = (a[9] - '0');
                }
                else{
                    f = (a[5] - '0');
                    if (isdigit(a[9])){
                        b = (a[8] - '0') * 10 + (a[9] - '0');
                    }
                    else b = (a[8] - '0');
                }
                printf("000001%s%s\n", ot[f], ot[b]);
            }
            else if (a[0] == 'S' && a[1] == 'U' && a[2] == 'B'){
                if (isdigit(a[6])){
                    f = (a[5] - '0') * 10 + (a[6] - '0');
                    if (isdigit(a[10])){
                        b = (a[9] - '0') * 10 + (a[10] - '0');
                    }
                    else b = (a[9] - '0');
                }
                else{
                    f = (a[5] - '0');
                    if (isdigit(a[9])){
                        b = (a[8] - '0') * 10 + (a[9] - '0');
                    }
                    else b = (a[8] - '0');
                }
                printf("000010%s%s\n", ot[f], ot[b]);
            }
            else if (a[0] == 'D' && a[1] == 'I' && a[2] == 'V'){
                if (isdigit(a[6])){
                    f = (a[5] - '0') * 10 + (a[6] - '0');
                    if (isdigit(a[10])){
                        b = (a[9] - '0') * 10 + (a[10] - '0');
                    }
                    else b = (a[9] - '0');
                }
                else{
                    f = (a[5] - '0');
                    if (isdigit(a[9])){
                        b = (a[8] - '0') * 10 + (a[9] - '0');
                    }
                    else b = (a[8] - '0');
                }
                printf("000011%s%s\n", ot[f], ot[b]);
            }
            else if (a[0] == 'M' && a[1] == 'U' && a[2] == 'L'){
                if (isdigit(a[6])){
                    f = (a[5] - '0') * 10 + (a[6] - '0');
                    if (isdigit(a[10])){
                        b = (a[9] - '0') * 10 + (a[10] - '0');
                    }
                    else b = (a[9] - '0');
                }
                else{
                    f = (a[5] - '0');
                    if (isdigit(a[9])){
                        b = (a[8] - '0') * 10 + (a[9] - '0');
                    }
                    else b = (a[8] - '0');
                }
                printf("000100%s%s\n", ot[f], ot[b]);
            }
            else if (a[0] == 'M' && a[1] == 'O' && a[2] == 'V' && a[3]=='E'){
                if (isdigit(a[7])){
                    f = (a[6] - '0') * 10 + (a[7] - '0');
                    if (isdigit(a[11])){
                        b = (a[10] - '0') * 10 + (a[11] - '0');
                    }
                    else b = (a[10] - '0');
                }
                else{
                    f = (a[6] - '0');
                    if (isdigit(a[10])){
                        b = (a[9] - '0') * 10 + (a[10] - '0');
                    }
                    else b = (a[9] - '0');
                }
                printf("000101%s%s\n", ot[f], ot[b]);
            }
            else if (a[0] == 'S' && a[1] == 'E' && a[2] == 'T'){
                if (isdigit(a[6])){
                    f = (a[5] - '0') * 10 + (a[6] - '0');
                }
                else{
                    f = (a[5] - '0');
                }
                printf("000110%s00000\n", ot[f], ot[b]);
            }
        }
        else {
            int x1=0, x2=0, x3=0;
            scanf("%6d%5d%5d", &x1, &x2, &x3);
            if (x1 == 1){
                if (x2 > 11111 || x2 == 0){
                    printf("Error!\n"); 
                    continue;
                }
                if (x3 > 11111 || x3 == 0){
                    printf("Error!\n");
                    continue;
                }
                int f = x2 / 10000 * 16 + x2 % 10000 / 1000 * 8 + x2 % 1000 / 100 * 4 + x2 % 100 / 10 * 2 + x2 % 10;
                int b  = x3 / 10000 * 16 + x3 % 10000 / 1000 * 8 + x3 % 1000 / 100 * 4 + x3 % 100 / 10 * 2 + x3 % 10;
                printf("ADD R%d,R%d\n", f, b);
            }
            else if (x1 == 10){
                if (x2 > 11111 || x2 == 0){
                    printf("Error!\n");
                    continue;
                }
                if (x3 > 11111 || x3 == 0){
                    printf("Error!\n");
                    continue;
                }
                int f = x2 / 10000 * 16 + x2 % 10000 / 1000 * 8 + x2 % 1000 / 100 * 4 + x2 % 100 / 10 * 2 + x2 % 10;
                int b = x3 / 10000 * 16 + x3 % 10000 / 1000 * 8 + x3 % 1000 / 100 * 4 + x3 % 100 / 10 * 2 + x3 % 10;
                printf("SUB R%d,R%d\n", f, b);
            }
            else if (x1 == 11){
                if (x2 > 11111 || x2 == 0){
                    printf("Error!\n");
                    continue;
                }
                if (x3 > 11111 || x3 == 0){
                    printf("Error!\n");
                    continue;
                }
                int f = x2 / 10000 * 16 + x2 % 10000 / 1000 * 8 + x2 % 1000 / 100 * 4 + x2 % 100 / 10 * 2 + x2 % 10;
                int b = x3 / 10000 * 16 + x3 % 10000 / 1000 * 8 + x3 % 1000 / 100 * 4 + x3 % 100 / 10 * 2 + x3 % 10;
                printf("DIV R%d,R%d\n", f, b);
            }
            else if (x1 == 100){
                if (x2 > 11111 || x2 == 0){
                    printf("Error!\n");
                    continue;
                }
                if (x3 > 11111 || x3 == 0){
                    printf("Error!\n");
                    continue;
                }
                int f = x2 / 10000 * 16 + x2 % 10000 / 1000 * 8 + x2 % 1000 / 100 * 4 + x2 % 100 / 10 * 2 + x2 % 10;
                int b = x3 / 10000 * 16 + x3 % 10000 / 1000 * 8 + x3 % 1000 / 100 * 4 + x3 % 100 / 10 * 2 + x3 % 10;
                printf("MUL R%d,R%d\n", f, b);
            }
            else if (x1 == 101){
                if (x2 > 11111 || x2 == 0){
                    printf("Error!\n");
                    continue;
                }
                if (x3 > 11111 || x3 == 0){
                    printf("Error!\n");
                    continue;
                }
                int f = x2 / 10000 * 16 + x2 % 10000 / 1000 * 8 + x2 % 1000 / 100 * 4 + x2 % 100 / 10 * 2 + x2 % 10;
                int b = x3 / 10000 * 16 + x3 % 10000 / 1000 * 8 + x3 % 1000 / 100 * 4 + x3 % 100 / 10 * 2 + x3 % 10;
                printf("MOVE R%d,R%d\n", f, b);
            }
            else if (x1 == 110){
                if (x2 > 11111 || x2 == 0){
                    printf("Error!\n");
                    continue;
                }
                if (x3 > 0){
                    printf("Error!\n");
                    continue;
                }
                int f = x2 / 10000 * 16 + x2 % 10000 / 1000 * 8 + x2 % 1000 / 100 * 4 + x2 % 100 / 10 * 2 + x2 % 10;
                //int b = x3 / 10000 * 16 + x3 % 10000 / 1000 * 8 + x3 % 1000 / 100 * 4 + x3 % 100 / 10 * 2 + x3 % 10;
                printf("SET R%d\n", f);
            }
            else printf("Error!\n");
        }
    }
    return 0;
}