#include //#include //#pragma GCC optimize("O2") using namespace std; #define reps(i,s,n) for(int i = s; i < n; i++) #define rep(i,n) reps(i,0,n) #define Rreps(i,n,e) for(int i = n - 1; i >= e; --i) #define Rrep(i,n) Rreps(i,n,0) #define ALL(a) a.begin(), a.end() using ll = long long; using vec = vector; using mat = vector; ll N,M,H,W,K,A,B; string S; using P = pair; const ll INF = (1LL<<60); template bool chmin(T &a, const T &b){ if(a > b) {a = b; return true;} else return false; } template bool chmax(T &a, const T &b){ if(a < b) {a = b; return true;} else return false; } template void print_vector(std::vector v,bool endline = true){ if(!v.empty()){ for(std::size_t i{}; i q) swap(p, q); return make_pair(p, q); }else { cout << "? " << i + 1 << ' ' << j + 1 << endl; int p, q; cin >> p >> q; return make_pair(p, q); } } vec calc(P p, int n, int o, bool pr = false){ vec res; rep(_, 2){ int nn = p.first, oo = p.second; nn += n; oo += o; if(pr) cout<= 1 && nn < N && oo >= 0 && oo < N)<= 1 && nn < N && oo >= 0 && oo < N) res.push_back(nn * N + oo); if(p.first == p.second) break; swap(p.first, p.second); } if(pr) print_vector(res); return res; } vec solve(){ map > id; reps(i, 1, N * N - N){ id[Q(i, 0)].push_back(i); } P big = id.rbegin()->first, small = id.begin()->first; if(N == 2){ if(small.first == -1) cout<<"! 3 2"<second[0], big_id = id.rbegin()->second[0]; if(small.first == 0){ one_bit = 0; n_bit = 1; }else if(big.first < 0){ one_bit = n_bit = N - 1; }else if(big.first - small.first == N - 1) { one_bit = -small.first; n_bit = 1 - small.second; }else{ one_bit = -small.second; n_bit = 1 - small.first; } vec ans(N * N - N); ans[0] = n_bit * N + one_bit; for(pair > pv : id){ vec kouho = calc(pv.first, n_bit, one_bit); if(debug && kouho.empty()){ cout<>N; solve(); /* random_device seed; mt19937 mt(seed()); uniform_int_distribution<> randN(3, 10), randA(0, 10000000); rep(_, 1000){ N = randN(mt); aite.resize(N * N - N); set a; reps(i, N, N * N) a.insert(i); Rreps(i, N * N - N + 1, 1){ int num = randA(mt)%i; auto ite = a.begin(); rep(j, num) ++ite; aite[N * N - N - i] = *ite; a.erase(ite); } vec res = solve(); if(aite != res){ print_vector(aite); print_vector(res); return 0; } } */ }