#include #define FOR(i, n) for(lli i = 0; i < (lli)(n); ++i) #define ALL(x) (x).begin(), (x).end() #define X(A) get<0>(A) #define Y(A) get<1>(A) #define Z(A) get<2>(A) #define W(A) get<3>(A) #define mt make_tuple #define mp make_pair using namespace std; using lli = long long int; using pii = pair; using piii = tuple; using vi = vector; using vii = vector; using viii = vector; using vvi = vector; using vvii = vector; using vviii = vector; using vb = vector; using vvb = vector; const int BOUND = 1000*1000; //const int BOUND = 5; int nbChairs; int ask(int x, int y) { printf("? %d %d\n", x, y); fflush(stdout); int out; scanf("%d", &out); return out; } struct Query { unordered_map memo; int query(int v) { if(memo.find(v) != memo.end()) return memo[v]; memo[v] = int_query(v); return memo[v]; } virtual int int_query(int v) = 0; }; struct RowQuery: public Query { int int_query(int v) { return ask(BOUND + 42, v); } }; struct ColQuery: public Query { int int_query(int v) { return ask(v, BOUND + 42); } }; struct FindQuery: public Query { vector rows, cols; vii prev; vector numInRow; int cRow, foundThisRow; FindQuery(): cRow(0), foundThisRow(0) {} int int_query(int v) { assert(v < (int)cols.size()); int ans = ask(cols[v], rows[cRow]); for(const pii& p: prev) if(p.second <= v && p.first < cRow) ans--; return ans; } void found(int col) { prev.push_back(mp(cRow, col)); memo.clear(); foundThisRow++; if(foundThisRow >= numInRow[cRow]) { cRow++; foundThisRow = 0; } } void addRow(int v) { if(rows.empty() || rows.back() != v) { rows.push_back(v); numInRow.push_back(1); } else numInRow.back()++; //printf("* Row %d (%d th)\n", v, numInRow.back()); } void addCol(int v) { if(cols.empty() || cols.back() != v) cols.push_back(v); //printf("* Col %d\n", v); } }; int dicho(Query* qu, int beg, int end, int seek) { if(end - beg == 1) return beg; int m = (beg + end) / 2 - 1; int mVal = qu->query(m); if(mVal >= seek) return dicho(qu, beg, m+1, seek); return dicho(qu, m+1, end, seek); } int main(void) { scanf("%d", &nbChairs); FindQuery qFind; RowQuery qRow; ColQuery qCol; FOR(i, nbChairs) { qFind.addRow(dicho(&qRow, -BOUND, BOUND+1, i+1)); qFind.addCol(dicho(&qCol, -BOUND, BOUND+1, i+1)); } FOR(i, nbChairs) { int col = dicho(&qFind, 0, qFind.cols.size(), qFind.foundThisRow + 1); qFind.found(col); } printf("!"); for(const pii& chair: qFind.prev) printf(" %d %d", qFind.cols[chair.second], qFind.rows[chair.first]); printf("\n"); fflush(stdout); return 0; }