Problem: Jury picked a polynomial f(x) = a_0 + a_1 ⋅ x + a_2 ⋅ x^2 + ... + a_k ⋅ x^k. k ≤ 10 and all a_i are integer numbers and 0 ≤ a_i < 10^6 + 3. It's guaranteed that there is at least one i such that a_i > 0.

Now jury wants you to find such an integer x_0 that f(x_0) ≡ 0 mod (10^6 + 3) or report that there is not such x_0.

You can ask no more than 50 queries: you ask value x_q and jury tells you value f(x_q) mod (10^6 + 3).

Note that printing the answer doesn't count as a query.

Interaction

To ask a question, print "? x_q" (0 ≤ x_q < 10^6 + 3). The judge will respond with a single integer f(x_q) mod (10^6 + 3). If you ever get a result of −1 (because you printed an invalid query), exit immediately to avoid getting other verdicts.

After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use: 

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



When you are ready to answer, print "! x_0" where x_0 is the answer or -1 if there is no such x_0.

You can ask at most 50 questions per test case.

Hack Format

To hack, use the following format.

The only line should contain 11 integers a_0, a_1, ..., a_{10} (0 ≤ a_i < 10^6 + 3, max_{0 ≤ i ≤ 10}{a_i} > 0) — corresponding coefficients of the polynomial.

Examples

Input


 
1000002

0


Output


? 0

? 1

! 1

Input


 
5

2

1



Output


? 2

? 1

? 0

! -1

Note

The polynomial in the first sample is 1000002 + x^2.

The polynomial in the second sample is 1 + x^2.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e6 + 3;
long long inv(long long a, long long b) {
  static vector<long long> u(3), m(3), d(3);
  u[0] = a;
  u[1] = 1;
  u[2] = 0;
  m[0] = b;
  m[1] = 0;
  m[2] = 1;
  while (u[0] % m[0] != 0) {
    long long n = u[0] / m[0];
    for (int i = 0; i < 3; i++) d[i] = u[i] - n * m[i];
    u = m;
    m = d;
  }
  return (m[1] + b) % b;
}
long long mod(long long v) { return ((v % MOD) + MOD) % MOD; }
long long sum(long long l, long long r) { return mod(l + r); }
long long mult(long long l, long long r) { return (l * r) % MOD; }
long long inverse(long long l) { return inv(l, MOD); }
bool equal(long long l, long long r) { return max(l, r) - min(l, r) == 0; }
double inverse(double l) { return 1.0 / l; }
double EPS = 1e-12;
bool equal(double l, double r) { return fabs(l - r) < EPS; }
template <typename T>
struct matrix {
  vector<vector<T>> in;
  int row, col;
  matrix(int row, int col, int op = 0)
      : row(row), col(col), in(row, vector<T>(col, 0)) {
    if (op)
      for (int i = 0; i < row; i++) in[i][i] = 1;
  }
  matrix(initializer_list<initializer_list<T>> c)
      : row(c.size()), col((*c.begin()).size()) {
    in = vector<vector<T>>(row, vector<T>(col, 0));
    int i, j;
    i = 0;
    for (auto &it : c) {
      j = 0;
      for (auto &jt : it) {
        in[i][j] = jt;
        j++;
      }
      i++;
    }
  }
  T &operator()(int i, int j) { return in[i][j]; }
  matrix<T> &operator*=(T t) {
    matrix<T> &l = *this;
    for (int i = 0; i < row; i++)
      for (int j = 0; j < col; j++) l(i, j) = mult(l(i, j), t);
    return l;
  }
  matrix<T> operator+(matrix<T> &r) {
    matrix<T> &l = *this;
    matrix<T> m(row, col, 0);
    for (int i = 0; i < row; i++)
      for (int j = 0; j < col; j++) m(i, j) = sum(l(i, j), r(i, j));
    return m;
  }
  matrix<T> operator*(matrix<T> &r) {
    matrix<T> &l = *this;
    int row = l.row;
    int col = r.col;
    int K = l.col;
    matrix<T> m(row, col, 0);
    for (int i = 0; i < row; i++)
      for (int k = 0; k < K; k++)
        for (int j = 0; j < col; j++)
          m(i, j) = sum(m(i, j), mult(l(i, k), r(k, j)));
    return m;
  }
  matrix<T> operator^(long long e) {
    matrix<T> &m = (*this);
    if (e == 0) return matrix(m.row, m.row, 1);
    if (e == 1) return m;
    if (e == 2) return m * m;
    auto m_ = m ^ (e / 2);
    m_ = m_ * m_;
    if (e % 2 == 1) m_ = m_ * m;
    return m_;
  }
  void multiply_r(int i, T k) {
    matrix<T> &m = (*this);
    for (int j = 0; j < col; j++) m(i, j) = mult(m(i, j), k);
  }
  void multiply_c(int j, T k) {
    matrix<T> &m = (*this);
    for (int i = 0; i < row; j++) m(i, j) = mult(m(i, j), k);
  }
  void sum_r(int i1, int i2, T k) {
    matrix<T> &m = (*this);
    for (int j = 0; j < col; j++) m(i1, j) = sum(m(i1, j), mult(k, m(i2, j)));
  }
  bool gaussian(int I, int J) {
    matrix<T> &m = (*this);
    T tmp = m(I, J);
    if (equal(tmp, 0)) return false;
    T tmp_ = inverse(tmp);
    multiply_r(I, tmp_);
    for (int i = 0; i < row; i++)
      if (i != I) sum_r(i, I, mult(-1, m(i, J)));
    return true;
  }
  T determinant() {
    matrix<T> m = (*this);
    for (int i = 0; i < row; i++)
      if (!m.gaussian(i, i)) return 0;
    T ans = 1;
    for (int i = 0; i < row; i++) ans = mult(ans, m(i, i));
    return ans;
  }
  matrix<T> inv() {
    matrix<T> &m = (*this);
    matrix<T> t(row, 2 * col, 0);
    for (int i = 0; i < row; i++)
      for (int j = 0; j < col; j++) t(i, j) = m(i, j);
    for (int i = 0; i < row; i++) t(i, row + i) = 1;
    for (int i = 0; i < row; i++) {
      if (!t.gaussian(i, i)) return matrix<T>(0, 0);
    }
    matrix<T> ans(row, col);
    for (int i = 0; i < row; i++)
      for (int j = 0; j < col; j++) ans(i, j) = t(i, row + j);
    return ans;
  }
};
template <typename T>
ostream &operator<<(ostream &out, matrix<T> &t) {
  for (int i = 0; i < t.row; i++) {
    for (int j = 0; j < t.col; j++) {
      cout << t(i, j) << " ";
    }
    cout << endl;
  }
  return out;
}
long long query(long long x) {
  cout << "? " << x << endl;
  long long y;
  cin >> y;
  return y;
}
long long eval(vector<long long> &coef, long long x) {
  long long curr = 1;
  int n = coef.size();
  long long ans = 0;
  for (int i = 0; i < n; i++) {
    ans = sum(ans, mult(coef[i], curr));
    curr = mult(curr, x);
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  matrix<long long> X(15, 15);
  matrix<long long> y(15, 1);
  for (int i = 0; i < 15; i++) {
    long long x = i;
    long long curr = 1;
    for (int j = 0; j < 15; j++) {
      X(i, j) = curr;
      curr = mult(curr, x);
    }
    y(i, 0) = query(x);
  }
  matrix<long long> X_ = X.inv();
  if (X_.row == 0) {
    cout << "! -1" << endl;
    exit(0);
  }
  matrix<long long> a = X_ * y;
  vector<long long> coef(15);
  for (int i = 0; i < 15; i++) coef[i] = a(i, 0);
  for (long long i = 0; i < MOD; i++) {
    if (eval(coef, i) == 0) {
      cout << "! " << i << endl;
      exit(0);
    }
  }
  cout << "! -1" << endl;
  exit(0);
}