#if 0 cat <mistaken-paste #endif // thx Ebi-chan! // #pragma GCC optimize("unroll-loops") // #pragma GCC optimize("O3") #pragma GCC diagnostic ignored "-Wincompatible-pointer-types" #define _USE_MATH_DEFINES #include #include #include #include #include #include #include #define BIG 2000000007LL #define VERYBIG 200000000000000007LL #define ULTRABIG 300000000000000000000LL #define MOD 1000000007LL #define FOD 998244353LL #define HOD 1000000009LL #define IOD 100000007LL typedef uint64_t ull; typedef int64_t sll; #define N_MAX 1048576 #ifdef __cplusplus #include #include // #include #include #include #include #include // #include // #include #include using std::queue; using std::priority_queue; using std::stack; // using std::tuple; using std::set; using std::map; using std::vector; using std::greater; using std::pair; using std::string; // using std::get; // using std::function; // using std::array; using std::cin; using std::cout; using std::endl; template pair operator+(pair l, pair r) { return pair(l.first + r.first, l.second + r.second); } #endif #ifndef M_PI #define M_PI 3.14159265358979323846264338327950 #endif typedef struct { sll a; sll b; } hwll; typedef struct { sll a; sll b; sll c; } hwllc; typedef struct { hwll a; hwll b; } linell; typedef struct { double a; double b; } hwreal; sll n, m; sll h, w; sll k; sll q; sll va, vb, vc, vd, ve, vf; ull ua, ub, uc, ud, ue, uf; long double vra, vrb, vrc; double vda, vdb, vdc; char ch, dh; ull umin (ull x, ull y) { return (x < y) ? x : y; } ull umax (ull x, ull y) { return (x > y) ? x : y; } sll smin (sll x, sll y) { return (x < y) ? x : y; } sll smax (sll x, sll y) { return (x > y) ? x : y; } double dmin (double x, double y) { return (x < y) ? x : y; } double dmax (double x, double y) { return (x > y) ? x : y; } ull gcd (ull x, ull y) { if (y == 0) { return x; } else { return gcd(y, x % y); } } ull bitpow (ull a, ull x, ull modulo) { ull result = 1; while (x) { if (x & 1) { result *= a; result %= modulo; } x /= 2; a = (a * a) % modulo; } return result; } ull divide (ull a, ull b, ull modulo) { return (a * bitpow(b, modulo - 2, modulo)) % modulo; } ull udiff (ull a, ull b) { if (a >= b) { return a - b; } else { return b - a; } } sll sdiff (sll a, sll b) { if (a >= b) { return a - b; } else { return b - a; } } int bitcount (ull n) { int result = 0; while (n) { if (n & 1) result++; n /= 2; } return result; } #define BEGCMP(NAME) int32_t NAME (const void *left, const void *right) #define DEFLR(TYPE) TYPE l=*(TYPE*)left,r=*(TYPE*)right #define CMPRET(L, R) if((L)<(R))return-1;if((L)>(R))return+1 // int32_t pullcomp (const void *left, const void *right) { // ull l = *(ull*)left; // ull r = *(ull*)right; // if (l < r) { // return -1; // } // if (l > r) { // return +1; // } // return 0; // } BEGCMP(pullcomp){ DEFLR(ull); CMPRET(l, r); return 0; } BEGCMP(prevcomp){ DEFLR(sll); CMPRET(r, l); return 0; } BEGCMP(psllcomp){ DEFLR(sll); CMPRET(l, r); return 0; } BEGCMP(pcharcomp){ DEFLR(char); CMPRET(l, r); return 0; } BEGCMP(pdoublecomp){ DEFLR(double); CMPRET(l, r); return 0; } int32_t pstrcomp (const void *left, const void *right) { char* l = *(char**)left; char* r = *(char**)right; return strcmp(l, r); } BEGCMP(phwllABcomp){ DEFLR(hwll); CMPRET(l.a, r.a); CMPRET(l.b, r.b); return 0; } BEGCMP(phwllREVcomp){ DEFLR(hwll); CMPRET(l.b, r.b); CMPRET(l.a, r.a); return 0; } BEGCMP(ptriplecomp){ DEFLR(hwllc); CMPRET(l.a, r.a); CMPRET(l.b, r.b); CMPRET(l.c, r.c); return 0; } BEGCMP(ptripleREVcomp){ DEFLR(hwllc); CMPRET(l.b, r.b); CMPRET(l.a, r.a); CMPRET(l.c, r.c); return 0; } BEGCMP(ptripleCABcomp){ DEFLR(hwllc); CMPRET(l.c, r.c); CMPRET(l.a, r.a); CMPRET(l.b, r.b); return 0; } BEGCMP(phwrealcomp){ DEFLR(hwreal); CMPRET(l.a, r.a); CMPRET(l.b, r.b); return 0; } int32_t pquadcomp (const void *left, const void *right) { linell l = *(linell*)left; linell r = *(linell*)right; sll ac = phwllABcomp(&(l.a), &(r.a)); if (ac) return ac; sll bc = phwllABcomp(&(l.b), &(r.b)); if (bc) return bc; return 0; } int32_t pfracomp (const void *left, const void *right) { hwll l = *(hwll*)left; hwll r = *(hwll*)right; CMPRET(l.a * r.b, l.b * r.a); return 0; } bool isinrange (sll left, sll x, sll right) { return (left <= x && x <= right); } bool isinrange_soft (sll left, sll x, sll right) { return (left <= x && x <= right) || (left >= x && x >= right); } void sw (sll *l, sll *r) { if (*l == *r) return; sll t = *l; *l = *r; *r = t; } void uw (ull *l, ull *r) { if (*l == *r) return; ull t = *l; *l = *r; *r = t; } ull frac[N_MAX * 10], invf[N_MAX * 10]; void f_init (sll n, sll m) { frac[0] = 1; for (sll i = 1; i <= n; i++) { frac[i] = frac[i - 1] * i % m; } invf[n] = divide(1, frac[n], m); for (sll i = n - 1; i >= 0; i--) { invf[i] = invf[i + 1] * (i + 1) % m; } } ull ncr (sll n, sll r, ull m) { if (n < 0 || r < 0 || n < r) return 0; return frac[n] * (invf[r] * invf[n - r] % m) % m; } sll a[N_MAX * 10]; // ull a[N_MAX + 5]; // sll a[3001][3001]; sll b[N_MAX * 5]; // ull b[N_MAX + 5]; // sll b[3001][3001]; sll c[N_MAX * 5]; sll d[N_MAX * 5]; sll e[N_MAX * 4]; char s[N_MAX + 1]; // char s[3010][3010]; char t[N_MAX + 1]; // char t[3010][3010]; char u[N_MAX + 1]; hwll xy[N_MAX]; hwllc tup[N_MAX]; // sll table[3005][3005]; sll table[2005][2005]; ull gin[N_MAX]; // here we go // ull parent[501910], size[501910], edges[501910]; // void init (ull n) { // for (sll i = 0; i < n; i++) { // parent[i] = i; // size[i] = 1; // } // } // sll find (ull x) { // if (parent[x] == x) return x; // return parent[x] = find(parent[x]); // } // bool unite (ull v, ull u) { // v = find(v); // u = find(u); // if (v == u) return false; // if (size[v] < size[u]) { // ull tmp = v; // v = u; // u = tmp; // } // size[v] += size[u]; // parent[u] = v; // return true; // } typedef pair P; map > mp; map cnt; sll solve () { sll i, j, ki, li; // ull result = 0; sll result = 0; double dresult = 0; // ull maybe = 0; sll maybe = 0; // ull sum = 0; sll sum = 0; sll item; sll *dpcell; mp[P(0, 0)].push_back(1LL); cnt[0] = 2; sll minv = VERYBIG, maxv = -VERYBIG; for (i = 2; i <= n * n - n; i++) { printf("? %lld %lld\n", i, 1LL); fflush(stdout); scanf("%lld%lld", &va, &vb); mp[P(va, vb)].push_back(i); cnt[va]++; cnt[vb]++; minv = smin(minv, va); maxv = smax(maxv, vb); } sll ox, oy; // ox = 1~N-1, oy = 0~N-1 if (cnt[minv] == n - 1) { oy = -minv; for (i = 0; i <= n - 1; i++) cnt[minv + i] -= (n - 1); sll collmin = VERYBIG; for (auto [key, val] : cnt) { // printf("%lld : %lld\n", key, val); if (val > 0) collmin = smin(collmin, key); } ox = -collmin + 1; } else { oy = (n - 1) - maxv; for (i = 0; i <= n - 1; i++) cnt[maxv - i] -= (n - 1); sll collmax = -VERYBIG; for (auto [key, val] : cnt) { // printf("%lld : %lld\n", key, val); if (val > 0) collmax = smax(collmax, key); } ox = (n - 1) - collmax; } // printf("%lld %lld...\n", ox, oy); for (auto [qr, list] : mp) { if (list.size() == 1) { if (isinrange(1, ox + qr.first, n - 1) && isinrange(0, oy + qr.second, n - 1)) { xy[list[0]].a = ox + qr.first; xy[list[0]].b = oy + qr.second; } else { xy[list[0]].a = ox + qr.second; xy[list[0]].b = oy + qr.first; } } else { printf("? %lld %lld\n", list[0], list[1]); fflush(stdout); scanf("%lld%lld", &va, &vb); sll ma = (ox + qr.first) - (ox + qr.second); sll mb = (oy + qr.second) - (oy + qr.first); if (ma > mb) { sll t = ma; ma = mb; mb = t; } if (ma == va && mb == vb) { xy[list[0]].a = ox + qr.first; xy[list[0]].b = oy + qr.second; xy[list[1]].a = ox + qr.second; xy[list[1]].b = oy + qr.first; } else { xy[list[1]].a = ox + qr.first; xy[list[1]].b = oy + qr.second; xy[list[0]].a = ox + qr.second; xy[list[0]].b = oy + qr.first; } } } putchar('!'); for (i = 1; i <= n * n - n; i++) { printf(" %lld", xy[i].a * n + xy[i].b); } putchar('\n'); // printf("%lld\n", result); // printf("%.15f\n", dresult); // puts(s); return 0; success: // puts("YES"); puts("Yes"); // printf("%lld\n", result); // puts("0"); // puts("First"); return 0; fail: // puts("NO"); puts("No"); // puts("0"); // puts("-1"); // puts("-1 -1 -1"); // puts(":("); return 1; } int main (int argc, char *argv[]) { int32_t i, j; // scanf("%llu", &m); // scanf("%lld", &w); // scanf("%lld%lld", &h, &w); scanf("%lld", &n, &m); // scanf("%lld", &k, &n, &m); // scanf("%llu%llu", &h, &w); // scanf("%lld", &q); // scanf("%lld%lld%lld", &va, &vb, &vc, &vd); // va--; // vb--; // scanf("%llu%llu%llu%llu", &ua, &ub, &uc, &ud, &ue); // scanf("%s", s); // scanf("%s", t); // scanf("%s", u); // scanf("%lld", &k); // scanf("%lld", &m); // scanf("%lld", &n); // for (i = 0; i < n; i++) { // // scanf("%s", s[i]); // // scanf("%lld", &c[i]); // scanf("%lld", &a[i]); // } // scanf(" %c", &ch); // scanf("%llu", &q); for (i = 0; i < 0; i++) { // scanf("%lld%lld", &xy[i].a, &xy[i].b); // scanf("%lld%lld%lld", &tup[i].a, &tup[i].b, &tup[i].c); // scanf("%lld", &c[i]); scanf("%lld", &a[i]); // scanf("%lld", &b[i]); // scanf("%lld", &c[i]); // scanf("%lld", &d[i]); // scanf("%lld", &e[i]); // a[i]--; // b[i]--; // c[i]--; // d[i]--; // xy[i].a--; // xy[i].b--; // tup[i].a--; // tup[i].b--; } // scanf("%lld%lld", &va, &vb); // scanf("%llu", &m); // scanf("%llu", &q); // scanf("%s", t); // for (i = 0; i < n; i++) { // // scanf("%lld%lld", &xy[i].a, &xy[i].b); // // xy[i].a--; // // xy[i].b--; // // scanf("%lld", &a[i], &b[i]); // // scanf("%lld", &b[i]); // // a[i]--; // // b[i]--; // scanf("%lld", &c[i]); // // scanf("%lld", &d[i]); // // scanf("%lld", &e[i]); // c[i]--; // // d[i]--; // } // for (i = 0; i < q; i++) { // // scanf("%lld%lld", &xy[i].a, &xy[i].b); // scanf("%lld", &c[i]); // // xy[i].a--; // // xy[i].b--; // } // for (i = 0; i < h; i++) { // for (j = 0; j < w; j++) { // scanf("%lld", &table[i][j]); // // table[i][j]--; // } // } // for (i = 0; i < n; i++) { // scanf("%s", s[i]); // } // for (i = 0; i < n; i++) { // scanf("%s", t[i]); // } // scanf("%llu", &q); // for (i = 0; i < q; i++) { // scanf("%lld%lld%lld", &e[i], &c[i], &d[i]); // c[i]--; // } solve(); return 0; }