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;
int n;
long long L;
long long l[1111], r[1111], f[1111];
bool cmp(int a, int b) { return f[a] == f[b] ? a < b : f[a] > f[b]; }
long long qtl = 1000000000000000000ll;
long long Query(int a, long long b) {
  printf("?\n%d %lld\n", a, b);
  fflush(stdout);
  long long f;
  scanf("%lld", &f);
  return f;
}
long long getX(int id, long long f, long long l, long long r) {
  int QAQ = 0;
  for (; l < r;) {
    ++QAQ;
    if (QAQ > 111) exit(25);
    long long mid = (l + r) >> 1;
    if (Query(id, mid) < f)
      l = mid + 1;
    else
      r = mid;
  }
  return l;
}
void solve(vector<int> x, long long l, long long r, int fl, int fr,
           int dep = 0) {
  if (dep > 233) exit(233);
  if (fr - fl != x.size()) exit(66);
  if (fr - fl == 0) return;
  if (fr - fl == 1) {
    ::l[x[0]] = l;
    ::r[x[0]] = r;
    return;
  }
  int fmid = (fl + fr) >> 1;
  int reql = fmid - fl;
  int reqr = fr - fmid;
  long long y;
  vector<int> vl, vr, cvl, cvr, vmid;
  int QAQ = 0;
  for (; x.size();) {
    int key = x[rand() % x.size()];
    y = getX(key, fmid * L, l, r);
    for (auto val : x) {
      long long qwq = Query(val, y);
      if (qwq > fmid * L) cvl.push_back(val);
      if (qwq == fmid * L) vmid.push_back(val);
      if (qwq < fmid * L) cvr.push_back(val);
    }
    if (cvl.size() + vl.size() > reql) {
      x = cvl;
      cvl.clear();
      for (auto val : vmid) vr.push_back(val);
      vmid.clear();
      for (auto val : cvr) vr.push_back(val);
      cvr.clear();
    } else if (cvr.size() + vr.size() > reqr) {
      x = cvr;
      cvr.clear();
      for (auto val : vmid) vl.push_back(val);
      vmid.clear();
      for (auto val : cvl) vl.push_back(val);
      cvl.clear();
    } else {
      for (auto val : cvl) vl.push_back(val);
      for (auto val : cvr) vr.push_back(val);
      int i = 0;
      for (; vl.size() < reql; ++i) vl.push_back(vmid[i]);
      for (; vr.size() < reqr; ++i) vr.push_back(vmid[i]);
      x.clear();
    }
    ++QAQ;
    if (QAQ > 111) exit(45);
  }
  solve(vl, l, y, fl, fmid, dep + 1);
  solve(vr, y, r, fmid, fr, dep + 1);
}
int main() {
  int seed = time(0) + (new char - (char*)NULL);
  srand(seed);
  scanf("%d%lld", &n, &L);
  L /= n;
  vector<int> qwq;
  for (int i = 1; i <= n; ++i) qwq.push_back(i);
  solve(qwq, 0, qtl, 0, n);
  puts("!");
  for (int i = 1; i <= n; ++i) printf("%lld %lld\n", l[i], r[i]);
  fflush(stdout);
  return 0;
}