#include using namespace std; struct Queries{ int n; vector> checked; vector> val; int cnt = 0; Queries(int _n) : n(_n) { checked.resize(n); val.resize(n); for (int i=0; i> x; val[i][j] = x; checked[i][j] = true; cnt++; return val[i][j]; } void answer(vector a, vector b){ cout << "! "; for (int i=0; i> n; if (n == 1){ cout << "! 1 1" << endl; return 0; } vector p(n+1, true); for (int i=2; i<=n; i++){ if (!p[i]) continue; for (int j=i*2; j<=n; j+=i){ p[j] = false; } } int P = -1; for (int i=n; i>=2; i--){ if (p[i]){ P = i; break; } } assert(P >= 2); // STEP 1 ... find max sosuu P less than or equal N either on A or B // if gcd(A[i], B) = P, then A[i] = P // if gcd(A[i], B[j]) = P * ??, then B[i] = P // // STEP 2 ... // WLOG assume A[i] = P // check all lcm(A[i], B[j]) // if (A[i], B[j]) = A[i] = P, then B[j] = 1 or P. // check lcm(A[k], B[j]) // // STEP 3 ... // you have B[j] = P, so check all. Queries que(n); int now = 0; vector a(n,-1), b(n,-1); for (int i=0; i kouho; char wherep; if (now == P){ wherep = 'A'; for (int i=0; i= 0); for (int i=0; i= 0); if (que.question(kouho[i], targ) % P == 0){ a[kouho[i]] = P; a[kouho[i^1]] = 1; }else{ a[kouho[i]] = 1; a[kouho[i^1]] = P; } break; } } //que.answer(a, b); { int targ = -1; for (int i=0; i= 1); for (int i=0; i= 1); for (int i=0; i as, bs; for (int i=0; i= 1); as.insert(a[i]); } for (int i=0; i= 1); bs.insert(b[i]); } assert((int)as.size() == n); assert((int)bs.size() == n); que.answer(a, b); }