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;
inline int rei() {
  int x;
  cin >> x;
  return x;
}
inline long long rel() {
  long long x;
  cin >> x;
  return x;
}
inline string res() {
  string x;
  cin >> x;
  return x;
}
long long Pow(long long X, long long R) {
  if (R == 0) {
    return 1;
  }
  if (R % 2 == 0) {
    long long T = Pow(X, R / 2);
    return T * T % 1000003;
  }
  return X * Pow(X, R - 1) % 1000003;
}
class LMOD {
 public:
  using t = long long;
  static t id() { return 0; }
  static t e() { return 1; }
  static t Prod(const t& l, const t& r) { return l * r % 1000003; }
  static t Plus(const t& l, const t& r) { return (l + r) % 1000003; }
  static t Minus(const t& x) { return (1000003 - x) % 1000003; }
  static t Divide(const t& x) { return Pow(x, 1000003 - 2); }
  static bool Smaller(const t& x, const t& y) { return x <= y; }
};
template <typename M>
struct Matrix {
  using T = typename M::t;
  int H;
  int W;
  vector<T> data;
  vector<T> L;
  vector<T> U;
  vector<int> S;
  Matrix(int n_) : H(n_), W(n_), data(n_ * n_, M::id()) {}
  Matrix(int h_, int w_) : H(h_), W(w_), data(h_ * w_, M::id()) {}
  Matrix(int n_, vector<T> d_) : H(n_), W(n_) { data = d_; }
  Matrix(int h_, int w_, vector<T> d_) : H(h_), W(w_) { data = d_; }
  void Update(int h, int w, T x) { data[h * W + w] = x; }
  const T Get(int h, int w) { return data[h * W + w]; }
  Matrix RowNormal() {
    vector<T> A(H * W);
    for (int i = 0; i < H * W; i++) {
      A[i] = data[i];
    }
    int rank = 0;
    for (int i = 0; i < W; i++) {
      int nonzero = rank;
      while (nonzero < H && A[nonzero * W + i] == M::id()) {
        nonzero++;
      }
      if (nonzero == H) {
        continue;
      }
      if (nonzero != rank) {
        for (int j = i; j < W; j++) {
          T temp = A[rank * W + j];
          A[rank * W + j] = A[nonzero * W + j];
          A[nonzero * W + j] = temp;
        }
      }
      {
        T d = M::Divide(A[rank * W + i]);
        for (int j = i; j < W; j++) {
          A[rank * W + j] = M::Prod(A[rank * W + j], d);
        }
      }
      for (int j = 0; j < H; j++) {
        if (j == rank) {
          continue;
        }
        T d = M::Minus(A[j * W + i]);
        for (int k = i; k < W; k++) {
          A[j * W + k] = M::Plus(A[j * W + k], M::Prod(A[rank * W + k], d));
        }
      }
      rank++;
    }
    Matrix ans(H, W, A);
    return ans;
  }
  int Rank() {
    int ans = 0;
    vector<T> A(H * W);
    vector<bool> used(H);
    for (int i = 0; i < H * W; i++) {
      A[i] = data[i];
    }
    for (int i = 0; i < W; i++) {
      int nonzero = 0;
      while (nonzero < H && (used[nonzero] || A[nonzero * W + i] == M::id())) {
        nonzero++;
      }
      if (nonzero == H) {
        continue;
      }
      ans++;
      used[nonzero] = true;
      for (int j = 0; j < H; j++) {
        if (used[j]) {
          continue;
        }
        T d = M::Minus(M::Prod(M::Divide(A[nonzero * W + i]), A[j * W + i]));
        for (int k = i; k < W; k++) {
          A[j * W + k] = M::Plus(A[j * W + k], M::Prod(A[nonzero * W + k], d));
        }
      }
    }
    return ans;
  }
  vector<T> GaussianEliminationO(vector<T> b) {
    int ans = 0;
    int N = H;
    vector<T> A(N * N);
    for (int i = 0; i < N * N; i++) {
      A[i] = data[i];
    }
    for (int i = 0; i < N; i++) {
      int maxj = i;
      for (int j = i + 1; j < N; j++) {
        if (M::Smaller(A[maxj * N + i], A[j * N + i])) {
          maxj = j;
        }
      }
      if (maxj != i) {
        for (int j = i; j < N; j++) {
          T temp = A[i * N + j];
          A[i * N + j] = A[maxj * N + j];
          A[maxj * N + j] = temp;
        }
        {
          T temp = b[i];
          b[i] = b[maxj];
          b[maxj] = temp;
        }
      }
      {
        T d = M::Divide(A[i * N + i]);
        for (int j = i; j < N; j++) {
          A[i * N + j] = M::Prod(A[i * N + j], d);
        }
        b[i] = M::Prod(b[i], d);
      }
      for (int j = 0; j < N; j++) {
        if (j == i) {
          continue;
        }
        T d = M::Minus(A[j * N + i]);
        for (int k = i; k < W; k++) {
          A[j * N + k] = M::Plus(A[j * N + k], M::Prod(A[i * N + k], d));
        }
        b[j] = M::Plus(b[j], M::Prod(b[i], d));
      }
    }
    return b;
  }
  vector<T> GaussianElimination(vector<T> b) {
    int ans = 0;
    int N = H;
    vector<T> A(N * N);
    for (int i = 0; i < N * N; i++) {
      A[i] = data[i];
    }
    for (int i = 0; i < N; i++) {
      int nonzeroj = 0;
      for (int j = i; j < N; j++) {
        if (A[j * N + i] != M::id()) {
          nonzeroj = j;
          break;
        }
      }
      if (nonzeroj != i) {
        for (int j = i; j < N; j++) {
          T temp = A[i * N + j];
          A[i * N + j] = A[nonzeroj * N + j];
          A[nonzeroj * N + j] = temp;
        }
        {
          T temp = b[i];
          b[i] = b[nonzeroj];
          b[nonzeroj] = temp;
        }
      }
      {
        T d = M::Divide(A[i * N + i]);
        for (int j = i; j < N; j++) {
          A[i * N + j] = M::Prod(A[i * N + j], d);
        }
        b[i] = M::Prod(b[i], d);
      }
      for (int j = 0; j < N; j++) {
        if (j == i) {
          continue;
        }
        T d = M::Minus(A[j * N + i]);
        for (int k = i; k < W; k++) {
          A[j * N + k] = M::Plus(A[j * N + k], M::Prod(A[i * N + k], d));
        }
        b[j] = M::Plus(b[j], M::Prod(b[i], d));
      }
    }
    return b;
  }
  static Matrix I(int N) {
    Matrix ans(N);
    for (int i = 0; i < N; i++) {
      ans.Update(i, i, M::e());
    }
    return ans;
  }
  static Matrix Plus(Matrix& A, Matrix& B) {
    int h = A.H;
    int w = A.W;
    Matrix ans(h, w);
    for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++) {
        ans.Update(i, j, M::Plus(A.Get(i, j), B.Get(i, j)));
      }
    }
    return ans;
  }
  static Matrix Minus(Matrix& A) {
    int h = A.H;
    int w = A.W;
    Matrix ans(h, w);
    for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++) {
        ans.Update(i, j, M::Minus(A.Get(i, j)));
      }
    }
    return ans;
  }
  static Matrix Minus(Matrix& A, Matrix& B) {
    int h = A.H;
    int w = A.W;
    Matrix ans(h, w);
    for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++) {
        ans.Update(i, j, M::Plus(A.Get(i, j), M::Minus(B.Get(i, j))));
      }
    }
    return ans;
  }
  static Matrix Prod(Matrix& A, Matrix& B) {
    int h = A.H;
    int w = B.W;
    int K = A.W;
    Matrix ans(h, w);
    for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++) {
        T c = M::id();
        for (int k = 0; k < K; k++) {
          c = M::Plus(c, M::Prod(A.Get(i, k), B.Get(k, j)));
        }
        ans.Update(i, j, c);
      }
    }
    return ans;
  }
  static Matrix Pow(Matrix A, long long r) {
    int n = A.H;
    vector<T> ans(n * n, M::id());
    for (int i = 0; i < n; i++) {
      ans[i * n + i] = M::e();
    }
    vector<T> ans2(n * n);
    vector<T> AP = A.data;
    vector<T> AP2(n * n);
    while (r) {
      if (r % 2 == 1) {
        for (int i = 0; i < n; i++) {
          for (int j = 0; j < n; j++) {
            T c = M::id();
            for (int k = 0; k < n; k++) {
              c = M::Plus(c, M::Prod(AP[i * n + k], ans[k * n + j]));
            }
            ans2[i * n + j] = c;
          }
        }
        swap(ans, ans2);
      }
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
          T c = M::id();
          for (int k = 0; k < n; k++) {
            c = M::Plus(c, M::Prod(AP[i * n + k], AP[k * n + j]));
          }
          AP2[i * n + j] = c;
        }
      }
      swap(AP, AP2);
      r /= 2;
    }
    Matrix answ(n, ans);
    return answ;
  }
  void LUDecompositionO() {
    int N = H;
    vector<T> A(N * N);
    L.resize(N * N);
    U.resize(N * N);
    S.resize(N);
    for (int i = 0; i < N * N; i++) {
      A[i] = data[i];
    }
    for (int i = 0; i < N; i++) {
      S[i] = i;
    }
    for (int i = 0; i < N; i++) {
      int maxline = i;
      for (int j = i + 1; j < N; j++) {
        if (M::Smaller(A[maxline * N + i], A[j * N + i])) {
          maxline = j;
        }
      }
      for (int j = 0; j < N; j++) {
        T temp = A[maxline * N + j];
        A[maxline * N + j] = A[i * N + j];
        A[i * N + j] = temp;
        temp = L[maxline * N + j];
        L[maxline * N + j] = L[i * N + j];
        L[i * N + j] = temp;
      }
      {
        int temp = S[maxline];
        S[maxline] = S[i];
        S[i] = temp;
      }
      L[i * N + i] = 1;
      U[i * N + i] = A[i * N + i];
      T aiiinv = M::Divide(A[i * N + i]);
      for (int j = i + 1; j < N; j++) {
        L[j * N + i] = M::Prod(A[j * N + i], aiiinv);
        U[i * N + j] = A[i * N + j];
      }
      for (int j = i + 1; j < N; j++) {
        for (int k = i + 1; k < N; k++) {
          A[j * N + k] = M::Plus(A[j * N + k],
                                 M::Minus(M::Prod(L[j * N + i], U[i * N + k])));
        }
      }
    }
  }
  void LUDecomposition() {
    int N = H;
    vector<T> A(N * N);
    L.resize(N * N);
    U.resize(N * N);
    S.resize(N);
    for (int i = 0; i < N * N; i++) {
      A[i] = data[i];
    }
    for (int i = 0; i < N; i++) {
      S[i] = i;
    }
    for (int i = 0; i < N; i++) {
      int nonzeroline = i;
      for (int j = i + 1; j < N; j++) {
        if (A[j * N + i] != M::id()) {
          nonzeroline = j;
        }
      }
      for (int j = 0; j < N; j++) {
        T temp = A[nonzeroline * N + j];
        A[nonzeroline * N + j] = A[i * N + j];
        A[i * N + j] = temp;
        temp = L[nonzeroline * N + j];
        L[nonzeroline * N + j] = L[i * N + j];
        L[i * N + j] = temp;
      }
      {
        int temp = S[nonzeroline];
        S[nonzeroline] = S[i];
        S[i] = temp;
      }
      L[i * N + i] = 1;
      U[i * N + i] = A[i * N + i];
      T aiiinv = M::Divide(A[i * N + i]);
      for (int j = i + 1; j < N; j++) {
        L[j * N + i] = M::Prod(A[j * N + i], aiiinv);
        U[i * N + j] = A[i * N + j];
      }
      for (int j = i + 1; j < N; j++) {
        for (int k = i + 1; k < N; k++) {
          A[j * N + k] = M::Plus(A[j * N + k],
                                 M::Minus(M::Prod(L[j * N + i], U[i * N + k])));
        }
      }
    }
  }
  vector<T> SolvebyLU(vector<T> b) {
    int N = H;
    vector<T> b2(N);
    for (int i = 0; i < N; i++) {
      b2[i] = b[S[i]];
    }
    for (int i = 0; i < N; i++) {
      T sum = b2[i];
      for (int j = 0; j < i; j++) {
        sum = M::Plus(sum, M::Minus(M::Prod(b[j], L[i * N + j])));
      }
      b[i] = sum;
    }
    for (int i = N - 1; i >= 0; i--) {
      T sum = b[i];
      for (int j = i + 1; j < N; j++) {
        sum = M::Plus(sum, M::Minus(M::Prod(b2[j], U[i * N + j])));
      }
      b2[i] = M::Prod(sum, M::Divide(U[i * N + i]));
    }
    return b2;
  }
};
void Calc() {
  const int N = 11;
  vector<long long> V(N * N);
  for (int i = 0; i < N; i++) {
    long long c = 1;
    for (int j = 0; j < N; j++) {
      V[i * N + j] = c;
      c *= i;
      c %= 1000003;
    }
  }
  Matrix<LMOD> Mat(N, V);
  Mat.LUDecomposition();
  vector<long long> B(N);
  for (int i = 0; i < N; i++) {
    cout << "? " << i << endl;
    B[i] = rei();
    if (B[i] == 0) {
      cout << "! " << i << endl;
      return;
    }
  }
  vector<long long> X = Mat.SolvebyLU(B);
  for (int i = 0; i < 1000003; i++) {
    long long c = 0;
    long long p = 1;
    for (int j = 0; j < N; j++) {
      c += X[j] * p % 1000003;
      p *= i;
      p %= 1000003;
    }
    c %= 1000003;
    if (c == 0) {
      cout << "! " << i << endl;
      return;
    }
  }
  cout << "! -1" << endl;
}
int main(int argc, char** argv) {
  ios::sync_with_stdio(false), cin.tie(0);
  cout.tie(0);
  Calc();
  return 0;
}