//team42 (Lukasz Zatorski, Damian Rusak, Krzysztof Piecuch) #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long int ll; typedef pair pi; typedef vector vi; typedef vector< vi > vii; #define ft first #define sd second #define mp make_pair #define pb push_back #define REP(i,a,b) for(register int i = a ; i < b; i++) #define DOWN(i,a,b) for(register int i = a; i>=b ; i--) #define WSK(C) typeof((C).begin()) #define FOREACH(wsk, C) for(WSK(C) wsk = (C).begin(); wsk!=(C).end; wsk++) int n,a,b,c,q,w,r,t,y; int M = 23; int rev(int x){ REP(i,1,M) if((x*i)%M == 1) return i; return 1; } int R[30]; vector >T; int B[60],V[60]; int N = 6; int P[100], E[100]; void Gauss(){ /*REP(i,0,N){ REP(j,0,N){ cout << T[i][j] << " "; } cout << " " << B[i] << endl; }*/ REP(i,0,N) REP(j,0,N) T[i][j] %= M; REP(i,0,N){ REP(j,i+1,N) if(T[j][i] != 0){ swap(T[i],T[j]); swap(B[i], B[j]); break; } if(T[i][i]==0) continue; REP(j,i+1,N){ int u = R[T[i][i]]*T[j][i]; REP(k,i,N) T[j][k] = (T[j][k] - u*T[i][k] + M*M*M)%M; B[j] = (B[j] - u*B[i] + M*M*M)%M; } /* REP(u,0,N){ REP(j,0,N){ cout << T[u][j] << " "; } cout << " " << B[u] << endl; }*/ } //najpierw zakl. ze nie ma wielu rozwiazan (wielomian!) REP(i,0,N) REP(j,0,N) T[i][j] = (T[i][j]+M*M*M)%M; DOWN(i,N-1,0){ int y = B[i]%M; REP(j,i+1,N) y = (y - V[j]*T[i][j] + M*M*M)%M; // cout << y << " " << T[i][i] << " " << R[T[i][i]] << endl; y = (y * R[T[i][i]] + M*M*M)%M; // cout << y << endl; V[i] = y%M; } //REP(i,0,N) cout << i << " " << V[i] << endl; } int main(){ REP(i,1,M) R[i] = rev(i); while(1){ scanf("%d", &n); if(n==1){ scanf("%d%d", &a,&b); if(a==b) { printf("END\n\n"); } else{ printf("NUM %d\nADD\nEND\n", b-a); } /* cout << n << endl; REP(i,0,n) cout << P[i] << endl; cout << endl;*/ continue; } if(n==0) break; REP(i,0,n){ scanf("%d%d", &P[i],&E[i]); } N = n; T.resize(N); REP(j,0,N) T[j].resize(n); REP(i,0,N){ B[i] = E[i]; REP(j,0,N) T[i][j] = pow(P[i], N-1-j)%M; } Gauss(); REP(i,0,N-2) printf("DUP\n"); printf("NUM %d\n", V[0]); printf("MUL\n"); REP(i,1,N-1) printf("NUM %d\nADD\nMUL\n", V[i]); printf("NUM %d\nADD\n",V[N-1]); printf("NUM 23\n"); printf("MOD\n"); printf("END\n"); /*cout << n << endl; REP(i,0,n) cout << P[i] << endl; cout << endl;*/ printf("\n"); } //cout << endl << "QUIT " << endl; return 0; }