Problem: We call a function good if its domain of definition is some set of integers and if in case it's defined in x and x-1, f(x) = f(x-1) + 1 or f(x) = f(x-1).

Tanya has found n good functions f_{1}, …, f_{n}, which are defined on all integers from 0 to 10^{18} and f_i(0) = 0 and f_i(10^{18}) = L for all i from 1 to n. It's an notorious coincidence that n is a divisor of L. 

She suggests Alesya a game. Using one question Alesya can ask Tanya a value of any single function in any single point. To win Alesya must choose integers l_{i} and r_{i} (0 ≤ l_{i} ≤ r_{i} ≤ 10^{18}), such that f_{i}(r_{i}) - f_{i}(l_{i}) ≥ L/n (here f_i(x) means the value of i-th function at point x) for all i such that 1 ≤ i ≤ n so that for any pair of two functions their segments [l_i, r_i] don't intersect (but may have one common point).

Unfortunately, Tanya doesn't allow to make more than 2 ⋅ 10^{5} questions. Help Alesya to win!

It can be proved that it's always possible to choose [l_i, r_i] which satisfy the conditions described above.

It's guaranteed, that Tanya doesn't change functions during the game, i.e. interactor is not adaptive

Input

The first line contains two integers n and L (1 ≤ n ≤ 1000, 1 ≤ L ≤ 10^{18}, n is a divisor of L) — number of functions and their value in 10^{18}.

Output

When you've found needed l_i, r_i, print "!" without quotes on a separate line and then n lines, i-th from them should contain two integers l_i, r_i divided by space.

Interaction

To ask f_i(x), print symbol "?" without quotes and then two integers i and x (1 ≤ i ≤ n, 0 ≤ x ≤ 10^{18}). Note, you must flush your output to get a response.

After that, you should read an integer which is a value of i-th function in point x.

You're allowed not more than 2 ⋅ 10^5 questions.

To flush you can use (just after printing an integer and end-of-line):

  * fflush(stdout) in C++; 
  * System.out.flush() in Java; 
  * stdout.flush() in Python; 
  * flush(output) in Pascal; 
  * See the documentation for other languages. 



Hacks:

Only tests where 1 ≤ L ≤ 2000 are allowed for hacks, for a hack set a test using following format:

The first line should contain two integers n and L (1 ≤ n ≤ 1000, 1 ≤ L ≤ 2000, n is a divisor of L) — number of functions and their value in 10^{18}.

Each of n following lines should contain L numbers l_1, l_2, ... , l_L (0 ≤ l_j < 10^{18} for all 1 ≤ j ≤ L and l_j < l_{j+1} for all 1 < j ≤ L), in i-th of them l_j means that f_i(l_j) < f_i(l_j + 1).

Example

Input


5 5
? 1 0
? 1 1
? 2 1
? 2 2
? 3 2
? 3 3
? 4 3
? 4 4
? 5 4
? 5 5
!
0 1
1 2
2 3
3 4
4 5


Output


0
1
1
2
2
3
3
4
4
4
5

Note

In the example Tanya has 5 same functions where f(0) = 0, f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 4 and all remaining points have value 5.

Alesya must choose two integers for all functions so that difference of values of a function in its points is not less than L/n (what is 1 here) and length of intersection of segments is zero.

One possible way is to choose pairs [0, 1], [1, 2], [2, 3], [3, 4] and [4, 5] for functions 1, 2, 3, 4 and 5 respectively.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <class T>
void splitstr(const string &s, vector<T> &out) {
  istringstream in(s);
  out.clear();
  copy(istream_iterator<T>(in), istream_iterator<T>(), back_inserter(out));
}
template <class T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
static void redirect(int argc, const char **argv) {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  if (argc > 1) {
    static filebuf f;
    f.open(argv[1], ios::in);
    cin.rdbuf(&f);
    if (!cin) {
      cerr << "Failed to open '" << argv[1] << "'" << endl;
      exit(1);
    }
  }
  if (argc > 2) {
    static filebuf f;
    f.open(argv[2], ios::out | ios::trunc);
    cout.rdbuf(&f);
    if (!cout) {
      cerr << "Failed to open '" << argv[2] << "'" << endl;
    }
  }
  cin.exceptions(ios::failbit);
}
static map<pair<long long, long long>, long long> cache;
static long long query(long long idx, long long pos) {
  pair<long long, long long> key(idx, pos);
  if (cache.count(key)) return cache[key];
  cout << "? " << idx + 1 << ' ' << pos << endl;
  long long ans;
  cin >> ans;
  cache[key] = ans;
  return ans;
}
static long long rev(int idx, long long trg, long long A, long long B) {
  while (B - A > 1) {
    long long M = (A + B) / 2;
    if (query(idx, M) >= trg)
      B = M;
    else
      A = M;
  }
  return B;
}
static mt19937 engine;
static constexpr long long BIG = 1000000000000000000LL;
static void recurse(vector<int> &funcs,
                    vector<pair<long long, long long> > &ranges, long long lo,
                    long long hi, long long P, long long Q) {
  if (((long long)(funcs).size()) == 1) {
    ranges[funcs[0]] = pair<long long, long long>(lo, hi);
    return;
  }
  long long N = ((long long)(funcs).size());
  long long N0 = N / 2;
  long long trg = P + (Q - P) / N * N0;
  int A = 0;
  int B = N;
  long long pos;
  while (true) {
    int M = uniform_int_distribution<int>(A, B - 1)(engine);
    swap(funcs[M], funcs[B - 1]);
    pos = rev(funcs[B - 1], trg, lo, hi);
    int g2 = partition(funcs.begin() + A, funcs.begin() + (B - 1),
                       [&](int i) { return query(i, pos) >= trg; }) -
             funcs.begin();
    swap(funcs[B - 1], funcs[g2]);
    int g1 = g2;
    while (g1 > A && query(funcs[g1 - 1], pos - 1) == trg - 1) {
      g1--;
    }
    if (g2 < N0)
      A = g2 + 1;
    else if (g1 > N0)
      B = g1;
    else
      break;
  }
  vector<int> f0(funcs.begin(), funcs.begin() + N0);
  vector<int> f1(funcs.begin() + N0, funcs.end());
  recurse(f0, ranges, lo, pos, P, trg);
  recurse(f1, ranges, pos, hi, trg, Q);
}
int main(int argc, const char **argv) {
  redirect(argc, argv);
  int N;
  long long L;
  cin >> N >> L;
  vector<int> funcs;
  vector<pair<long long, long long> > ranges(N);
  for (int i = 0; i < N; i++) funcs.push_back(i);
  recurse(funcs, ranges, 0, BIG, 0, L);
  cout << "!" << endl;
  for (int i = 0; i < N; i++) {
    assert(ranges[i].first < ranges[i].second);
    cout << ranges[i].first << ' ' << ranges[i].second << endl;
  }
  return 0;
}