/** * date : 2020-12-11 00:55:09 */ #define NDEBUG using namespace std; // intrinstic #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include // utility namespace Nyaan { using ll = long long; using i64 = long long; using u64 = unsigned long long; using i128 = __int128_t; using u128 = __uint128_t; template using V = vector; template using VV = vector>; using vi = vector; using vl = vector; using vd = V; using vs = V; using vvi = vector>; using vvl = vector>; template struct P : pair { template P(Args... args) : pair(args...) {} using pair::first; using pair::second; T &x() { return first; } const T &x() const { return first; } U &y() { return second; } const U &y() const { return second; } P &operator+=(const P &r) { first += r.first; second += r.second; return *this; } P &operator-=(const P &r) { first -= r.first; second -= r.second; return *this; } P &operator*=(const P &r) { first *= r.first; second *= r.second; return *this; } P operator+(const P &r) const { return P(*this) += r; } P operator-(const P &r) const { return P(*this) -= r; } P operator*(const P &r) const { return P(*this) *= r; } }; using pl = P; using pi = P; using vp = V; constexpr int inf = 1001001001; constexpr long long infLL = 4004004004004004004LL; template int sz(const T &t) { return t.size(); } template void mem(T (&a)[N], int c) { memset(a, c, sizeof(T) * N); } template inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; } template inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; } template int lb(const vector &v, const T &a) { return lower_bound(begin(v), end(v), a) - begin(v); } template int ub(const vector &v, const T &a) { return upper_bound(begin(v), end(v), a) - begin(v); } constexpr long long TEN(int n) { long long ret = 1, x = 10; for (; n; x *= x, n >>= 1) ret *= (n & 1 ? x : 1); return ret; } template pair mkp(const T &t, const U &u) { return make_pair(t, u); } template vector mkrui(const vector &v, bool rev = false) { vector ret(v.size() + 1); if (rev) { for (int i = int(v.size()) - 1; i >= 0; i--) ret[i] = v[i] + ret[i + 1]; } else { for (int i = 0; i < int(v.size()); i++) ret[i + 1] = ret[i] + v[i]; } return ret; }; template vector mkuni(const vector &v) { vector ret(v); sort(ret.begin(), ret.end()); ret.erase(unique(ret.begin(), ret.end()), ret.end()); return ret; } template vector mkord(int N, F f) { vector ord(N); iota(begin(ord), end(ord), 0); sort(begin(ord), end(ord), f); return ord; } template vector reord(const vector &v, const vector &ord) { int N = v.size(); vector ret(N); for (int i = 0; i < N; i++) ret[i] = v[ord[i]]; return ret; }; template vector mkiota(int N) { vector ret(N); iota(begin(ret), end(ret), 0); return ret; } template vector mkinv(vector &v, int max_val = -1) { if (max_val < (int)v.size()) max_val = v.size() - 1; vector inv(max_val + 1, -1); for (int i = 0; i < (int)v.size(); i++) inv[v[i]] = i; return inv; } } // namespace Nyaan // bit operation namespace Nyaan { __attribute__((target("popcnt"))) inline int popcnt(const u64 &a) { return _mm_popcnt_u64(a); } __attribute__((target("bmi"))) inline int lsb(const u64 &a) { return _tzcnt_u64(a); } __attribute__((target("bmi"))) inline int ctz(const u64 &a) { return _tzcnt_u64(a); } __attribute__((target("lzcnt"))) inline int msb(const u64 &a) { return 63 - _lzcnt_u64(a); } __attribute__((target("lzcnt"))) inline int clz64(const u64 &a) { return _lzcnt_u64(a); } template inline int gbit(const T &a, int i) { return (a >> i) & 1; } template inline void sbit(T &a, int i, bool b) { a ^= (gbit(a, i) == b ? 0 : (T(b) << i)); } constexpr long long PW(int n) { return 1LL << n; } constexpr long long MSK(int n) { return (1LL << n) - 1; } } // namespace Nyaan // inout namespace Nyaan { template ostream &operator<<(ostream &os, const pair &p) { os << p.first << " " << p.second; return os; } template istream &operator>>(istream &is, pair &p) { is >> p.first >> p.second; return is; } template ostream &operator<<(ostream &os, const vector &v) { int s = (int)v.size(); for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i]; return os; } template istream &operator>>(istream &is, vector &v) { for (auto &x : v) is >> x; return is; } void in() {} template void in(T &t, U &... u) { cin >> t; in(u...); } void out() { cout << "\n"; } template void out(const T &t, const U &... u) { cout << t; if (sizeof...(u)) cout << sep; out(u...); } void outr() {} template void outr(const T &t, const U &... u) { cout << t; outr(u...); } struct IoSetupNya { IoSetupNya() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(7); } } iosetupnya; } // namespace Nyaan // debug namespace DebugImpl { template struct is_specialize : false_type {}; template struct is_specialize< U, typename conditional::type> : true_type {}; template struct is_specialize< U, typename conditional::type> : true_type {}; template struct is_specialize::value, void>> : true_type { }; void dump(const char& t) { cerr << t; } void dump(const string& t) { cerr << t; } template ::value, nullptr_t> = nullptr> void dump(const U& t) { cerr << t; } template void dump(const T& t, enable_if_t::value>* = nullptr) { string res; if (t == Nyaan::inf) res = "inf"; if (is_signed::value) if (t == -Nyaan::inf) res = "-inf"; if (sizeof(T) == 8) { if (t == Nyaan::infLL) res = "inf"; if (is_signed::value) if (t == -Nyaan::infLL) res = "-inf"; } if (res.empty()) res = to_string(t); cerr << res; } template void dump(const pair&); template void dump(const pair&); template void dump(const T& t, enable_if_t::value>* = nullptr) { cerr << "[ "; for (auto it = t.begin(); it != t.end();) { dump(*it); cerr << (++it == t.end() ? "" : ", "); } cerr << " ]"; } template void dump(const pair& t) { cerr << "( "; dump(t.first); cerr << ", "; dump(t.second); cerr << " )"; } template void dump(const pair& t) { cerr << "[ "; for (int i = 0; i < t.second; i++) { dump(t.first[i]); cerr << (i == t.second - 1 ? "" : ", "); } cerr << " ]"; } void trace() { cerr << endl; } template void trace(Head&& head, Tail&&... tail) { cerr << " "; dump(head); if (sizeof...(tail) != 0) cerr << ","; trace(forward(tail)...); } } // namespace DebugImpl #ifdef NyaanDebug #define trc(...) \ do { \ cerr << "## " << #__VA_ARGS__ << " = "; \ DebugImpl::trace(__VA_ARGS__); \ } while (0) #else #define trc(...) #endif // macro #define each(x, v) for (auto&& x : v) #define each2(x, y, v) for (auto&& [x, y] : v) #define all(v) (v).begin(), (v).end() #define rep(i, N) for (long long i = 0; i < (long long)(N); i++) #define repr(i, N) for (long long i = (long long)(N)-1; i >= 0; i--) #define rep1(i, N) for (long long i = 1; i <= (long long)(N); i++) #define repr1(i, N) for (long long i = (N); (long long)(i) > 0; i--) #define reg(i, a, b) for (long long i = (a); i < (b); i++) #define regr(i, a, b) for (long long i = (b)-1; i >= (a); i--) #define repc(i, a, cond) for (long long i = (a); (cond); i++) #define enm(i, val, vec) \ for (long long i = 0; i < (long long)(vec).size(); i++) \ if (auto& val = vec[i]; false) \ ; \ else #define ini(...) \ int __VA_ARGS__; \ in(__VA_ARGS__) #define inl(...) \ long long __VA_ARGS__; \ in(__VA_ARGS__) #define ins(...) \ string __VA_ARGS__; \ in(__VA_ARGS__) #define inc(...) \ char __VA_ARGS__; \ in(__VA_ARGS__) #define in2(s, t) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i]); \ } #define in3(s, t, u) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i]); \ } #define in4(s, t, u, v) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i], v[i]); \ } #define die(...) \ do { \ Nyaan::out(__VA_ARGS__); \ return; \ } while (0) namespace Nyaan { void solve(); } int main() { Nyaan::solve(); } // using namespace Nyaan; pi send(int x, int y) { cout << "? " << x << " " << y << endl; ini(p, q); return mkp(p, q); } void Nyaan::solve() { ini(N); int M = N * N - N; vi ans(M, -1); V ret; ret.emplace_back(0, 0); rep1(i, M - 1) ret.emplace_back(send(1, i + 1)); auto f = [&](int a, int b) -> pi { int x = a / N - b / N, y = a % N - b % N; return minmax(x, y); }; trc(ret); auto xs = ret; sort(all(xs)); rep(i, M) { V X; rep(j, M) { X.push_back(f(i + N, j + N)); } sort(all(X)); trc(X); if (X == xs) { ans[0] = i + N; break; } } trc(ans[0]); auto id = [&](int x, int y) { if (0 < x and x < N and 0 <= y and y < N) return x * N + y; return -1; }; auto inv = [&](pi p) -> vi { trc(p); int x0 = ans[0] / N, y0 = ans[0] % N; int xa = x0 - p.x(), ya = y0 - p.y(); int xb = x0 - p.y(), yb = y0 - p.x(); trc(xa, ya, xb, yb); int a = id(xa, ya), b = id(xb, yb); vi res; if (a != -1) res.push_back(a); if (b != a and b != -1) res.push_back(b); return res; }; map mp; rep(i, M) mp[ret[i]].push_back(i); queue> Q; each(p, mp) Q.push(p); while (!Q.empty()) { auto [p, v] = Q.front(); Q.pop(); auto ns = inv(p); trc(p, v, ns); if(v.size() != ns.size()){ int i = 0; for(int i = 0;;i++); cout << i << endl; } if (sz(v) == 1) { ans[v.back()] = ns.back(); } else { int ok = 0; rep(i, M) { if (ans[i] == -1) continue; auto f0 = f(ans[i], ns[0]); auto f1 = f(ans[i], ns[1]); if (f0 != f1) continue; auto rs = send(i, v[0]); assert(rs == f0 or rs == f1); if (rs == f1) swap(v[0], v[1]); ans[v[0]] = ns[0], ans[v[1]] = ns[1]; ok = 1; break; } if (!ok) Q.emplace(p, v); } } cout << "! " << ans << endl; }