#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define debug 0
#define YES cout << "Yes" << endl;
#define NO cout << "No" << endl;
using ll = long long;
using ld = long double;
const int mod = 998244353;
const int MOD = 1000000007;
const double pi = atan2(0, -1);
const int inf = (1 << 31) - 1;
const ll INF = (1LL << 63)-1;
#include <time.h>
#include <chrono>
#include <atcoder/convolution>
#include <atcoder/modint>
using namespace atcoder;



//vectorの中身を空白区切りで出力
template<typename T> 
void print1(vector<T> v) {
	for (int i = 0; i < v.size(); i++) {
		cout << v[i];
		if (i < v.size() - 1) {
			cout << " ";
		}
	}
}

//vectorの中身を改行区切りで出力
template<typename T>
void print2(vector<T> v) {
	for (auto x : v) {
		cout << x << endl;
	}
}

//二次元配列を出力
template<typename T>
void printvv(vector<vector<T>> vv) {
	for (vector<T> v : vv) {
		print1(v);
		cout << endl;
	}
}

//vectorを降順にソート
template<typename T>
void rsort(vector<T> &v) {
	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());
}

//昇順priority_queueを召喚
template<typename T>
struct rpriority_queue {
	priority_queue<T, vector<T>, greater<T>> pq;

	void push(T x) {
		pq.push(x);
	}

	void pop() {
		pq.pop();
	}

	T top() {
		return pq.top();
	}

	size_t size() {
		return pq.size();
	}

	bool empty() {
		return pq.empty();
	}
};


//高速10^n計算(mod mod)
ll tenth(int n) {
	if (n == 0) {
		return 1;
	}
	else if (n % 2 == 0) {
		ll x = tenth(n / 2);
		x %= mod;
		x *= x;
		x %= mod;
		return x;
	}
	else {
		ll x = tenth(n - 1);
		x *= 10;
		x %= mod;
		return x;
	}
}


//高速a^n計算
ll power(int a, int n){
	if(n == 0){
		return 1;
	}
	else if(n % 2 == 0){
		ll x = power(a, n / 2);
		x *= x;
		return x;
	}
	else {
		ll x = power(a, n - 1);
		x *= a;
		return x;
	}
}
ld power(ld a, int n){
	if(n==0){
		return 1;
	}
	else if(n%2==0){
		ld t=power(a,n/2);
		return t*t;
	}
	else{
		return a*power(a,n-1);
	}
}

//n以下の素数列を生成
vector<int> prime (int n) {
	vector<bool> ch(n, false);
	vector<int> pr;
	for(int i = 2; i <= n; i++){
		if(!ch[i]){
			pr.push_back(i);
			for(int j = 1; i*j<=n; j++){
				ch[i*j]=true;
			}
		}
	}
	return pr;
}

//最大公約数(ユークリッドの互除法）
ll gcd (ll a, ll b){
	if(b>a){
		swap(a, b);
	}
	while(a%b!=0){
		ll t = a;
		a = b;
		b = t%b;
	}
	return b;
}

//最小公倍数（gcdを定義しておく）
ll lcm (ll a, ll b){
	ll g = gcd(a, b);
	ll x = (a/g)*b;
	return x;
}


//N以上の最小の2冪を返す
ll upper_binary(ll N){
	ll ret=1;
	while(ret<N) ret<<=1LL;
	return ret;
}

//__int128_tの準備
// abs overload for __int128_t to avoid ambiguous call with std::abs
static inline __int128_t abs128(__int128_t x) noexcept {
	return x < 0 ? -x : x;
}

// gcd for __int128_t
static inline __int128_t gcd128(__int128_t a, __int128_t b) noexcept {
	if (a < 0) a = -a;
	if (b < 0) b = -b;
	while (b != 0) {
		__int128_t t = a % b;
		a = b;
		b = t;
	}
	return a;
}

ostream& operator<< (ostream& os, __int128_t a){
	vector<int8_t> v;
	__int128_t b=::abs(a);
	while(b>0){
		v.push_back(b%10);
		b/=10;
	}
	string ret;
	if(a<0){
		ret+='-';
	}
	for(int i=v.size()-1;i>=0;i--){
		ret+=char('0'+v[i]);
	}
	if(ret.length()==0){
		ret+='0';
	}
	os << ret;
	return os;
}



//有理数クラス
class Ratio{
	public:
		Ratio(__int128_t _numerator=0, __int128_t _denominator=1){
			numerator=_numerator;
			denominator=_denominator;
			standardize();
		}

		bool operator== (const Ratio& a) const{
			return (a.numerator==numerator) && (a.denominator==denominator);
		}

		bool operator!= (const Ratio& a) const{
			return (a.numerator!=numerator) || (a.denominator!=denominator); 
		}

		Ratio operator+ (const Ratio& a) const{
			Ratio res(numerator*a.denominator+a.numerator*denominator, denominator*a.denominator);
			return res;
		}

		Ratio& operator+= (const Ratio& a){
			numerator=numerator*a.denominator+a.numerator*denominator;
			denominator*=a.denominator;
			standardize();
			return *this;
		}

		Ratio operator- (const Ratio& a) const{
			Ratio res(numerator*a.denominator - a.numerator*denominator, denominator*a.denominator);
			return res;
		}

		Ratio& operator-= (const Ratio& a){
			numerator=numerator*a.denominator-a.numerator*denominator;
			denominator*=a.denominator;
			standardize();
			return *this;
		}

		Ratio operator* (const Ratio& a) const{
			Ratio res(numerator*a.numerator, denominator*a.denominator);
			return res;
		}

		Ratio& operator*= (const Ratio& a){
			numerator*=a.numerator;
			denominator*=a.denominator;
			standardize();
			return *this;
		}

		Ratio operator/ (const Ratio& a) const{
			Ratio res(numerator*a.denominator, denominator*a.numerator);
			return res;
		}

		Ratio& operator/= (const Ratio& a){
			numerator*=a.denominator;
			denominator*=a.numerator;
			standardize();
			return *this;
		}

		bool operator< (const Ratio& a) const {
			return numerator*a.denominator < a.numerator*denominator;
		}

		bool operator<=(const Ratio& a) const {
			return numerator*a.denominator <= a.numerator*denominator;
		}

		bool operator> (const Ratio& a) const{
			return numerator*a.denominator > a.numerator*denominator;
		}

		bool operator>= (const Ratio& a) const{
			return numerator*a.denominator >= a.numerator*denominator;
		}

		Ratio& operator= (const Ratio& a){
			numerator=a.numerator;
			denominator=a.denominator;
			return *this;
		}

		ld to_ld(){
			return ld(numerator)/ld(denominator);
		}

		double to_double(){
			return double(numerator)/double(denominator);
		}

		// 自身以下の最大の整数を返す
		ll le_integer(){
			ll ret=0;
			if(denominator==1){
				ret=numerator;
			}
			else{
				if(numerator<0){
					ret=numerator/denominator-1;
				}
				else{
					ret=numerator/denominator;
				}
			}
			return ret;
		}

		// 自身以上の最小の整数を返す
		ll ge_integer(){
			ll ret=0;
			if(denominator==1){
				ret=numerator;
			}
			else{
				if(numerator<0){
					ret=numerator/denominator;
				}
				else{
					ret=numerator/denominator+1;
				}
			}
			return ret;
		}

		// 自身の逆数を返す。0なら0を返す
		Ratio inverse(){
			if(numerator==0){
				return Ratio(0,1);
			}
			else{
				return Ratio(denominator,numerator);
			}
		}

		friend ostream& operator<< (ostream& os, const Ratio& a);

	private:
		__int128_t numerator;
		__int128_t denominator;

		void standardize(){
			__int128_t g = gcd128(abs128(numerator), abs128(denominator));
			if(g==0){
				numerator=0;
				denominator=1;
			}
			else{
				numerator/=g;
				denominator/=g;
				if((numerator<0)^(denominator<0)){
					numerator=abs128(numerator)*-1;
					denominator=abs128(denominator);
				}
				else{
					numerator=abs128(numerator);
					denominator=abs128(denominator);
				}
			}
		}

};

ostream& operator<< (ostream& os, const Ratio& a){
	os << a.numerator << "/" <<a.denominator;
	return os;
}

Ratio power(Ratio a, int n){
	if(n==0){
		return Ratio(1,1);
	}
	else if(n%2==0){
		Ratio t=power(a,n/2);
		return t*t;
	}
	else{
		return a*power(a,n-1);
	}
}



//角XYZ(偏角Z→X)の角度（[0,2π)）
double angle(vector<double> X, vector<double> Y, vector<double>Z) {
	vector<double> x = { X[0] - Y[0],X[1] - Y[1] };
	vector<double> z = { Z[0] - Y[0],Z[1] - Y[1] };

	double pre, post;
	pre = atan2(x[1], x[0]);
	post = atan2(z[1], z[0]);
	if (post < 0) {
		post += pi*2;
	}
	if (pre < 0) {
		pre += pi*2;
	}
	if (pre < post) {
		pre += pi * 2;
	}
	return pre - post;
}

//mod mod下で逆元を算出する
//高速a^n計算(mod ver.)
ll mypower(ll a, ll n, ll Mod=mod) {
	if (n == 0) {
		return 1;
	}
	else if (n % 2 == 0) {
		ll x = mypower(a, n / 2,Mod);
		x *= x;
		x %= Mod;
		return x;
	}
	else {
		ll x = mypower(a, n - 1,Mod);
		x *= a;
		x %= Mod;
		return x;
	}
}
//フェルマーの小定理を利用
ll fmodinv(ll p, ll Mod=mod) {
	return mypower(p, Mod - 2,Mod) % Mod;
}

//拡張ユークリッドの互除法によるmod p下逆元
ll modinv(ll a, ll Mod=mod){
	ll x,y;
	// ax + by = 1 の解を[x,y]に格納し、gcd(a,b)を返す:gcdは常に一定
	function<ll(ll,ll)> extgcd=[&](ll a, ll b){

		if(b==0){
			x=1; y=0;
			return a;
		}
		else{
			ll g=extgcd(b, a%b);
			swap(x,y);
			y-=(a/b)*x;
			return g;
		}
	};
	ll g = extgcd(Mod, a);
	if(g==1){
		return (Mod+y%Mod)%Mod;
	}
	else{
		return 0;
	}
}


//整数係数不定方程式 a*x + b*y = cの解[x,y]の一つを見つける。解が無いと[INF,INF]を返す
vector<ll> solve_indefinite_eq(ll a, ll b, ll c){
	ll x,y;
	function<ll(ll,ll)> extgcd=[&](ll a,ll b){
		if(b==0){
			x=1; y=0;
			return a;
		}
		else{
			ll g=extgcd(b,a%b);
			swap(x,y);
			y -= (a/b)*x;
			return g;
		}
	};
	ll g=extgcd(a,b);
	if(c%g==0){
		return {(c/g)*x, (c/g)*y};
	}
	else{
		return {INF,INF};
	}
}

////素因数分解（osa_k法）（前計算O(N)、素数判定O(1)、素因数分解(O(logN)） //エラトステネスの篩の代わりとしても使える(N項のvectorを生成するため、巨大数に対しては√Nまでの素数リストを作って割る方が良い)
struct osa_k {
	//最大値までの各自然数に対し、その最小の素因数を格納するリスト
	vector<int> min_prime_list;
	int upper_limit;
	osa_k(int N) {
		//N:最大値。一つの自然数の素因数分解にしか興味が泣ければそれを入力
		vector<int> v(N + 1);
		upper_limit = N;
		rep(i, N + 1) {
			v[i] = i;
		}
		swap(min_prime_list, v);

		//k=2から見る
		for (int k = 2; k * k <= N; k++) {
			if (min_prime_list[k] == k) {
				//最小の素因数=自分ならば、素数
				//kが素数の時、t=k*kから始めてt=Nまでのkの倍数全てを確認する。未更新の自然数があれば、それの最小の素因数をkに更新する。
				//k*k未満のkの倍数に対しては、kが最小の素因数にはなり得ないので計算する必要が無い
				for (int t = k * k; t <= N; t += k) {
					if (min_prime_list[t] == t) {
						min_prime_list[t] = k;
					}
				}
			}
		}
	}

	//任意の自然数nが素数であればtrueを返す
	bool isPrime(int n) {
		if (n < 2) {
			return false;
		}
		else {
			return min_prime_list[n] == n;
		}
	}

	//任意の自然数nの素因数分解を行う。素因数はvectorで与えられる（ex:n=12 -> {2,2,3}）
	vector<int> divPrimes(int n) {
		vector<int> vec;
		int now = n;
		while (now > 1) {
			vec.push_back(min_prime_list[now]);
			now /= min_prime_list[now];
		}
		return vec;
	}
};


//最大流問題を解く構造体(Ford-Fulkerson法.O(FE))
struct maxflow {
	struct Edge {
		int to, rev;
		ll capacity, init_capacity;
		int off, on;
		Edge(int _to, int _rev, ll _capacity, int _off, int _on) :to(_to), rev(_rev), capacity(_capacity), init_capacity(_capacity), off(_off), on(_on) {};
	};
	int delay=0;
	
	vector<vector<Edge>> Graph;

	maxflow(int MAX_V, int d) {
		Graph.assign(MAX_V, {});
		delay=d;
	}

	void input(int from, int to, ll capacity, int off, int on) {
		int e_id = Graph[from].size();
		int r_id = Graph[to].size();
		Graph[from].push_back(Edge(to, r_id, capacity, off, on));
		Graph[to].push_back(Edge(from, e_id, 0, on+delay, off-delay));
	}

	Edge& rev_Edge(Edge& edge) {
		return Graph[edge.to][edge.rev];
	}

	vector<bool> visited;
	ll dfs(int now, int g, ll flow, int time) {
		visited[now] = true;
		if (now == g) {
			return flow;
		}
		else {
			ll f = 0;
			ll res_flow = flow;
			for (Edge& edge : Graph[now]) {
				if (!visited[edge.to] && edge.capacity > 0 && edge.off>=time && edge.on<=1e9) {
					ll f_delta = dfs(edge.to, g, min(res_flow, edge.capacity), edge.on+delay);	
					edge.capacity -= f_delta;
					rev_Edge(edge).capacity += f_delta;
					f += f_delta;
					res_flow -= f_delta;
					if (res_flow == 0) {
						break;
					}
				}
			}
			return f;
		}
	}

	void flowing(int s, int g, ll init_flow = INF) {
		bool cont = true;
		while (cont) {
			visited.assign(Graph.size(), false);
			ll flow = dfs(s, g, init_flow,0);
			init_flow -= flow;
			if (flow == 0) {
				cont = false;
			}
		}
	}

	ll get_flow(int g) {
		ll flow = 0;
		for (Edge& edge : Graph[g]) {
			Edge& rev_edge = rev_Edge(edge);
			ll tmp_flow = rev_edge.init_capacity - rev_edge.capacity;
			if (tmp_flow > 0) {
				flow += tmp_flow;
			}
		}
		return flow;
	}

	vector<tuple<int, int, ll>> flowing_edges() {
		vector<tuple<int, int, ll>> vec;
		rep(from, Graph.size()) {
			for (Edge& edge : Graph[from]) {
				ll flow = edge.init_capacity - edge.capacity;
				if (flow > 0) {
					vec.push_back({ from,edge.to,flow });
				}
			}
		}
		return vec;
	}
};

//Dinic法でのmax-flow。最大マッチングなど辺のキャパシティが小さい場合には高速
struct Dinic {
	struct Edge {
		int to, rev;
		ll capacity, init_capacity;
		ld cost;
		Edge(int _to, int _rev, ll _capacity,ld _cost) :to(_to), rev(_rev), capacity(_capacity),init_capacity(_capacity),cost(_cost) {};
	};

	vector<vector<Edge>> Graph;

	Edge& rev_Edge(Edge& edge) {
		return Graph[edge.to][edge.rev];
	}
	vector<int> level,itr;

	Dinic(int MAX_V) {
		Graph.assign(MAX_V, {});
	}

	void input(int _from, int _to, ll _capacity,ld _cost) {
		int e_id = Graph[_from].size(), r_id = Graph[_to].size();
		Graph[_from].push_back(Edge(_to, r_id, _capacity,_cost));
		Graph[_to].push_back(Edge(_from, e_id, 0LL,_cost));
	}

	void bfs(int s, int g, ld val) {
		level.assign(Graph.size(), -1);
		level[s] = 0;
		queue<int> q;
		q.push(s);
		while (!q.empty()) {
			int now = q.front();
			q.pop();
			if (now == g) {
				continue;
			}
			for (Edge &e : Graph[now]) {
				if (level[e.to] == -1 && e.capacity > 0 && e.cost<=val) {
					level[e.to] = level[now] + 1;
					q.push(e.to);
				}
			}
		}
	}

	ll dfs(int now, int g, ll flow, ld val) {
		if (now == g) {
			return flow;
		}
		else if (level[now] >= level[g]) {
			return 0; //gよりも深い場所に行こうとしたら終わり。flow=0を返す
		}
		else {
			ll res_flow = flow;
			ll f = 0;
			for (int &i = itr[now]; i < Graph[now].size(); i++) {
				Edge& edge = Graph[now][i];
				if (level[edge.to] == level[now] + 1 && edge.capacity > 0 && edge.cost<=val) {
					ll f_delta = dfs(edge.to, g, min(res_flow, edge.capacity), val);
					edge.capacity -= f_delta;
					rev_Edge(edge).capacity += f_delta;
					res_flow -= f_delta;
					f += f_delta;
					if (res_flow == 0) {
						break;
					}
				}
			}
			return f; //行先が無い場合はflow=0を返す
		}
	}

	void flowing(int s, int g, ll init_flow = INF, ld val=0) {
		bool cont1 = true;
		while (cont1) {
			bfs(s, g,val);
			if (level[g] == -1) {
				cont1 = false;
			}
			else {
				bool cont2 = true;
				while (cont2) {
					itr.assign(Graph.size(), 0);
					ll flow = dfs(s, g, init_flow,val);
					init_flow -= flow;
					if (flow == 0) {
						cont2 = false;
					}
				}
			}
			if(init_flow==0){
				cont1=false;
			}
		}
	}

	ll get_flow(int g) {
		ll flow = 0;
		for (Edge& edge : Graph[g]) {
			flow += max(0LL, rev_Edge(edge).init_capacity - rev_Edge(edge).capacity);
		}
		return flow;
	}

	vector<tuple<int, int, ll>> flowing_edges(){
		vector<tuple<int,int,ll>> vec;
		for (int from = 0; from < Graph.size(); from++) {
			for (Edge& edge : Graph[from]) {
				if (edge.init_capacity - edge.capacity > 0) {
					vec.push_back({ from,edge.to,edge.init_capacity - edge.capacity });
				}
			}
		}
		return vec;
	}

	void reset() {
		for (int from = 0; from < Graph.size(); from++) {
			for (Edge& edge : Graph[from]) {
				edge.capacity = edge.init_capacity;
			}
		}
	}
};

//小さい方/大きい方からk番目の値を取り出せる平衡二分木
template <typename T>
struct ordered_set{
  struct node{
    T val; //載せたい値。不等式で順序が定義されるものにする
    int prio; //優先度（ランダムに付与される。平衡化するために必要）
    int id; //この頂点のindex
    int par; //親のindex
    int cl; //子の内小さい方のindex
    int cr; //子の内大きい方のindex
    int size; //この頂点を根とする部分木の大きさ
    bool survive; //eraseされたらfalseになる
    node(int _val=0,int _id=-1, int _par=-1, int _cl=-1, int _cr=-1){
      val=_val;
      id=_id;
      prio=rand();
      par=_par;
      cl=_cl;
      cr=_cr;
      size=1;
      survive=true;
    }
  };

  vector<node> tree;
  int root;

  ordered_set(){
    srand(int(time(NULL)));
    tree={};
    root=-1;
  }

	int size(){
		return root==-1?0:tree[root].size;
	}

  int calc_size(node &n){
    int ret=1;
    if(n.cl!=-1){
      ret+=tree[n.cl].size;
    }
    if(n.cr!=-1){
      ret+=tree[n.cr].size;
    }
    n.size=ret;
    return ret;
  }

  int find(T val){
    int now=root;
    while(now!=-1){
      if(tree[now].val==val){
        break;
      }
      if(tree[now].val>=val){
        now=tree[now].cl;
      }
      else{
        now=tree[now].cr;
      }
    }
    return now;
  }

  bool count(T val){
		int id=find(val);
		if(id==-1 || !tree[id].survive){
			return false;
		}
		else{
			return true;
		}
  }

	bool empty(){
		return size()==0;
	}

  void rotate(node &c, node &p){
    if(p.par!=-1){
      if(tree[p.par].cl==p.id){
        tree[p.par].cl=c.id;
      }
      else{
        tree[p.par].cr=c.id;
      }
    }
    if(c.val<=p.val){
      if(c.cr!=-1){
        tree[c.cr].par=p.id;
      }
      p.cl=c.cr;
      c.cr=p.id;
      c.par=p.par;
      p.par=c.id;
    }
    else{
      if(c.cl!=-1){
        tree[c.cl].par=p.id;
      }
      p.cr=c.cl;
      c.cl=p.id;
      c.par=p.par;
      p.par=c.id;
    }
		calc_size(p);
  }

  void add_child(node &c, node &p){
    c.par=p.id;
    if(c.val<=p.val){
      p.cl=c.id;
    }
    else{
      p.cr=c.id;
    }
    p.size++;
  }

  bool insert(T val){
    int id=find(val);

		if(id==-1){
			tree.push_back(node(val, tree.size()));
			node &neo=tree[tree.size()-1];
			if(root==-1){
				root=neo.id;
			}
			else{
				int p=root;
				while(true){
					tree[p].size++;
					int c;
					if(tree[p].val>=val){
						c=tree[p].cl;
					}
					else{
						c=tree[p].cr;
					}
					if(c!=-1){
						p=c;
					}
					else{
						break;
					}
				}
				add_child(neo, tree[p]);
				while(neo.par!=-1){
					if(tree[neo.par].prio>neo.prio){
						break;
					}
					else{
						rotate(neo, tree[neo.par]);
					}
				}
				calc_size(neo);

				if(neo.par==-1){
					root=neo.id;
				}
			}
			return true;
		}

		else if(tree[id].survive){
			return false;
		}

		else {
			tree[id].survive=true;
			int now=id;
			while(now!=-1){
				tree[now].size++;
				now=tree[now].par;
			}
			return true;
		}
  }

  bool erase(T val){
    int id=find(val);
    if(id==-1){
      return false;
    }
		else if(!tree[id].survive){
			return false;
		}
    else{
      tree[id].survive=false;
      int now=id;
      while(now!=-1){
        tree[now].size--;
        now=tree[now].par;
      }

      return true;
    }
  }

  T find_kth_min(int k){
    assert(k<=size());
    int now=root;
    while(true){
			if(tree[now].survive){
				int tmp=1;
				if(tree[now].cl!=-1){
					tmp+=tree[tree[now].cl].size;
				}
				if(tmp==k){
					break;
				}
				else if(tmp<k){
					k-=tmp;
					now=tree[now].cr;
				}
				else{
					now=tree[now].cl;
				}
			}
			else{
				int tmp=0;
				if(tree[now].cl==-1){
					now=tree[now].cr;
				}
				else if(tree[now].cr==-1){
					now=tree[now].cl;
				}
				else{
					if(tree[tree[now].cl].size>=k){
						now=tree[now].cl;
					}
					else{
						k-=tree[tree[now].cl].size;
						now=tree[now].cr;
					}
				}
			}
    }
    return tree[now].val;
  }

  T find_kth_max(int k){
    assert(k<=size());
    int now=root;
    while(true){
			if(tree[now].survive){
				int tmp=1;
				if(tree[now].cr!=-1){
					tmp+=tree[tree[now].cr].size;
				}
				if(tmp==k){
					break;
				}
				else if(tmp<k){
					k-=tmp;
					now=tree[now].cl;
				}
				else{
					now=tree[now].cr;
				}
			}
			else{
				int tmp=0;
				if(tree[now].cr==-1){
					now=tree[now].cl;
				}
				else if(tree[now].cl==-1){
					now=tree[now].cr;
				}
				else{
					if(tree[tree[now].cr].size>=k){
						now=tree[now].cr;
					}
					else{
						k-=tree[tree[now].cr].size;
						now=tree[now].cl;
					}
				}
			}
    }
    return tree[now].val;
  }

	int lower_count(T val){
		//valより小さい値の個数を返す
		int ret=0;
		int now=root;
		while(now!=-1){
			if(tree[now].val<val){
				if(tree[now].cl!=-1){
					ret+=tree[tree[now].cl].size;
				}
				now=tree[now].cr;
			}
			else{
				now=tree[now].cl;
			}
		}
		return ret;
	}

	int lower_or_equal_count(T val){
		//val以下の値の個数を返す
		int ret=0;
		int now=root;
		while(now!=-1){
			if(tree[now].val<=val){
				if(tree[now].cl!=-1){
					ret+=tree[tree[now].cl].size;
				}
				if(tree[now].survive){
					ret++;
				}
				now=tree[now].cr;
			}
			else{
				now=tree[now].cl;
			}
		}
		return ret;
	}

	int upper_count(T val){
		//valより大きい値の個数を返す
		return tree[root].size - lower_or_equal_count(val);
	}

	int upper_or_equal_count(T val){
		//val以上の値の個数を返す
		return tree[root].size - lower_count(val);
	}
};

//Z-algorithm: 長さNの配列（主に文字列）を渡したとき、i番目の要素から始まる連続部分列のprefixと元の配列のprefixの最長一致数を配列として出力する
template <typename T>
vector<int> Zalgorithm(T &V){
	int n=V.size();
	vector<int> prefix_length(n,0);
	prefix_length[0]=n;
	function<void (int,int)> calc=[&](int start, int range_end){
		if(start>=n){
			return;
		}
		int wide=range_end-start;
		while(start+wide<n && V[wide]==V[start+wide]){
			wide++;
		}
		prefix_length[start]=wide;
		for(int i=0;i<wide;i++){
			if(i+prefix_length[i]<wide){
				prefix_length[start+i]=prefix_length[i];
			}
			else if(i+prefix_length[i]>wide){
				prefix_length[start+i]=wide-i;
			}
			else{
				calc(start+i, start+wide-1);
				return;
			}
		}
		int next=max(start+1, start+wide);
		calc(next,next);
		return;
	};
	calc(1,1);
	return prefix_length;
}

// オイラーツアーできる木構造:共通最小祖先（LCA）
struct EulerTour{
	vector<vector<int>> edge;
	vector<int> par;
	vector<vector<int>> child;
	int n;
	int root;
	struct move{
		int from;
		int to;
		move(int _from, int _to):from(_from), to(_to){};
	};
	struct node{
		int in=-1;
		int out=-1;
		int depth=-1;
	};

	vector<move> moves;
	vector<node> nodes;


	struct segtree{
		struct stnode{
			int index;
			int depth;
			stnode(int _index=-1, int _depth=inf):index(_index), depth(_depth){};
		};

		stnode min(stnode a, stnode b){
			if(a.depth<=b.depth){
				return a;
			}
			else{
				return b;
			}
		};

		vector<stnode> tree;
		int stn=1;

		segtree(int N=2){
			while(stn<N){
				stn*=2;
			}
			tree.assign(stn*2, stnode());
		}

		void input(int step, int index, int depth){
			int now=stn-1+step;
			tree[now].depth=depth;
			tree[now].index=index;
			while(now>0){
				now = (now-1)/2;
				tree[now]=min(tree[now*2+1], tree[now*2+2]);
			}
		}

		stnode Min(int l, int r, int b, int u, int now){

			stnode ret;
			if(l>=u || r<=b){
				ret = stnode();
			}
			else if(l<= b && r>=u){
				ret = tree[now];
			}
			else{
				ret = min(Min(l,r,b,(b+u)/2,now*2+1), Min(l,r,(b+u)/2,u,now*2+2));
			}
			return ret;
		}

		stnode queryMin(int l, int r){
			return Min(l,r,0,stn,0);
		}
	};

	segtree st;

	EulerTour(int N){
		n=N;
		edge.assign(n,{});
		par.assign(n,-1);
		child.assign(n,{});
		nodes.assign(n,node());
		st = segtree(n*2);
	}

	void inputEdge(int a, int b){
		edge[a].push_back(b);
		edge[b].push_back(a);
	}

	void _createTree(int _root=0){
		root=_root;
		par[root]=root;
		queue<int> q;
		q.push(0);
		while(!q.empty()){
			int now=q.front();
			q.pop();
			for(int x:edge[now]){
				if(par[x]==-1){
					par[x]=now;
					child[now].push_back(x);
					q.push(x);
				}
			}
		}
	}

	void tour(int _root=0){
		_createTree(_root);
		int step=0;
		moves.push_back(move(-1,root));
		function<void(int, int)> dfs = [&](int now, int depth){
			nodes[now].in=step;
			nodes[now].depth=depth;
			step++;
			for(int x:child[now]){
				moves.push_back(move(now, x));
				dfs(x,depth+1);
			}
			nodes[now].out=step;
			moves.push_back(move(now, par[now]));
			step++;
		};
		dfs(root,0);
		rep(i,moves.size()){
			st.input(i,moves[i].to, nodes[moves[i].to].depth);
		}
	}

	int lca(int x, int y){
		int mini = min(nodes[x].in, nodes[y].in);
		int maxi=max(nodes[x].out, nodes[y].out);
		return st.queryMin(mini,maxi).index;
	}
};


//抽象化セグメント木1 - 一点更新区間取得
template <typename T>
struct absSegTree{
	vector<T> tree;
	int n=1;
	T def;
	absSegTree(int N, T _default){
		while(n<N){
			n*=2;
		}
		def=_default;
		tree.assign(n*2, _default);
	}

	//値a,bから計算結果を返す
	virtual T get_op(T a, T b){
		T ret;
		return ret;
	}

  //値更新の計算
	virtual T update_op(T pre_value, T delta){
		T ret;
		return ret;
	}

	void input(int i, T val){
		int now=n-1+i;
		tree[now]=val;
		while(now>0){
			now=(now-1)/2;
			tree[now]=get_op(tree[now*2+1], tree[now*2+2]);
		}
	}

	void update_query(int i, T x){
		int now=n-1+i;
		tree[now]=update_op(tree[now], x);
		while(now>0){
			now=(now-1)/2;
			tree[now]=get_op(tree[now*2+1], tree[now*2+2]);
		}
	}

	T range_val(int l, int r, int b, int u, int now){
		if(l>=u || r<=b){
			return def;
		}
		else if(l<=b && r>=u){
			return tree[now];
		}
		else{
			return get_op(range_val(l,r,b,(b+u)/2,now*2+1),range_val(l,r,(b+u)/2,u,now*2+2));
		}
	}

	T get_query(int l, int r){
		return range_val(l,r,0,n,0);
	}
};

//抽象化セグメント木2 - 区間更新一点取得(双対セグメント木)
template<typename T>
struct absDualSegTree{
	vector<T> tree;
	int n=1;
	T def;
	absDualSegTree(int N, T _default){
		while(n<N){
			n*=2;
		}
		def=_default;
		tree.assign(n*2,def);
	}

	//作用素ツリーの更新
	virtual T update_op(T a, T b){
		T ret;
		return ret;
	}

	//作用素を作用させた結果を返す
	virtual T get_op(T pre_value, T f){
		T ret;
		return ret;
	}

	void input(int i, T val){
		int now=n-1+i;
		tree[now]=val;
	}

	void range_update(int l, int r, int b, int u, T x, int now){
		if(l>=u || r<= b){
			return;
		}
		else if(l<=b && r>=u){
			tree[now]=update_op(tree[now], x);
		}
		else{
			range_update(l,r,b,(b+u)/2,x,now*2+1);
			range_update(l,r,(b+u)/2,u,x,now*2+2);
		}
	}

	void update_query(int l, int r, T x){
		range_update(l,r,0,n,x,0);
	}

	T get_query(int i){
		int now=n-1+i;
		T ret=get_op(def,tree[now]);
		while(now>0){
			now=(now-1)/2;
			ret=get_op(ret,tree[now]);
		}
		return ret;
	}
};

//抽象化遅延伝搬セグメント木 - 区間更新区間取得（Lazy Segment Tree）
template<typename treeT, typename lazyT>
struct absLazySegTree{
	vector<treeT> tree;
	vector<lazyT> lazy;
	int n=1;
	treeT tree_default;
	lazyT lazy_default;
	
	absLazySegTree(int N, treeT _tree_default=0, lazyT _lazy_default=0):tree_default(_tree_default), lazy_default(_lazy_default){
		while(n<N){
			n*=2;
		}
		tree.assign(n*2, tree_default);
		lazy.assign(n*2, _lazy_default);
	}

	void input(int i, treeT x){
		int now=n-1+i;
		tree[now]=x;
		while(now>0){
			now=(now-1)/2;
			tree[now]=get_op(tree[now*2+1],tree[now*2+2]);
		}
	}

	// lazy-treeの作用素同士の結合写像
	virtual lazyT lazy_update_op(lazyT pre, lazyT delta){
		return lazy_default;
	}

	// lazy-treeの作用素をtreeのノードに作用させる写像
	virtual treeT lazy_to_tree_op(int now, treeT pre, lazyT delta){
		return tree_default;
	}

	// 2つのtreeのノードを合成する写像
	virtual treeT get_op(treeT a, treeT b){
		return tree_default;
	}
	

	void update_query(int l, int r, lazyT x){
		lazy_update(l,r,0,n,0,x);
	}

	treeT get_query(int l, int r){
		pre_get(l,r,0,n,0);
		return tree_get(l,r,0,n,0);
	}

	private: 
		void lazy_update(int l, int r, int b, int u, int now, lazyT x){
			if(l>=u || r<=b){
				if(lazy[now]!=lazy_default){
					tree[now]=lazy_to_tree_op(now, tree[now],lazy[now]);
					lazy_propagate(now);
				}
			}
			else if(l<=b && r>=u){
				lazy[now]=lazy_update_op(lazy[now], x);
				if(lazy[now]!=lazy_default){
					tree[now]=lazy_to_tree_op(now, tree[now],lazy[now]);
					lazy_propagate(now);
				}
			}
			else{
				if(lazy[now]!=lazy_default){
					lazy_propagate(now);	
				}
				lazy_update(l,r,b,(b+u)/2,now*2+1,x);
				lazy_update(l,r,(b+u)/2,u,now*2+2,x);
				tree[now]=get_op(tree[now*2+1],tree[now*2+2]);
			}
		}

		void lazy_propagate(int now){
			if(now<n-1){
				lazy[now*2+1]=lazy_update_op(lazy[now*2+1], lazy[now]);
				lazy[now*2+2]=lazy_update_op(lazy[now*2+2], lazy[now]);
			}
			lazy[now]=lazy_default;
		}

		void pre_get(int l, int r, int b, int u, int now){
			if(l>=u || r<=b){
				if(lazy[now]!=lazy_default){
					tree[now]=lazy_to_tree_op(now, tree[now], lazy[now]);
					lazy_propagate(now);
				}
			}
			else if(l<=b && r>=u){
				if(lazy[now]!=lazy_default){
					tree[now]=lazy_to_tree_op(now, tree[now], lazy[now]);
					lazy_propagate(now);
				}
			}
			else{
				if(lazy[now]!=lazy_default){
					lazy_propagate(now);
				}
				pre_get(l,r,b,(b+u)/2,now*2+1);
				pre_get(l,r,(b+u)/2,u,now*2+2);
				tree[now]=get_op(tree[now*2+1],tree[now*2+2]);
			}
		}

		treeT tree_get(int l, int r, int b, int u, int now){
			if(l>=u || r<=b){
				return tree_default;
			}
			else if(l<=b && r>=u){
				return tree[now];
			}
			else{
				return get_op(tree_get(l,r,b,(b+u)/2,now*2+1), tree_get(l,r,(b+u)/2,u,now*2+2));
			}
		}
};

//永続セグメント木 - バージョン管理できるセグ木 一点更新区間取得
template<typename T>
struct absPerSegTree{
	T def;
	int n=1;
	struct node{
		T value;
		int par;
		int left;
		int right;
		node(T v, int p=-1, int l=-1, int r=-1):par(p),left(l),right(r){
			value=v;
		}
	};
	vector<node> tree;
	unordered_map<int,int> version_root;

	absPerSegTree(int N, T _default){
		def=_default;
		while(n<N) n<<=1;
		node def_node(def);
		tree.assign(n*2, def_node);
		rep(now,n*2-1){
			if(now!=0){
				tree[now].par=(now-1)/2;
			}
			if(now<n-1){
				tree[now].left=now*2+1;
				tree[now].right=now*2+2;
			}
		}
		version_root[0]=0;
	}

	void input(int i, T x){
		int now=n-1+i;
		tree[now]=x;
		while(now>0){
			now=(now-1)/2;
			tree[now].value=get_op(tree[now*2+1].value, tree[now*2+2].value);
		}
	}
	
	void update_query(int i, T x, int pre_version, int neo_version){
		int l=0, r=n;
		int pre_now=version_root[pre_version];
		version_root[neo_version]=tree.size();
		int neo_now=-1;
		int neo_par=-1;
		while(true){
			tree.push_back(tree[pre_now]);
			neo_now=tree.size()-1;
			tree[neo_now].par=neo_par;
			if(r>l+1){
				if((l+r)/2>i){
					// leftに移動
					tree[neo_now].left=tree.size();
					pre_now=tree[pre_now].left;
					r=(l+r)/2;
				}
				else{
					// rightに移動
					tree[neo_now].right=tree.size();
					pre_now=tree[pre_now].right;
					l=(l+r)/2;
				}
				neo_par=neo_now;
			}
			else{
				break;
			}
		}

		tree[neo_now].value=update_op(tree[neo_now].value, x);
		while(neo_now!=version_root[neo_version]){
			neo_now=tree[neo_now].par;
			tree[neo_now].value=get_op(tree[tree[neo_now].left].value,tree[tree[neo_now].right].value);
		}
	}

	T _get(int l, int r, int b, int u, int now){
		if(l>=u || r<=b){
			return def;
		}
		else if(l<=b && r>=u){
			return tree[now].value;
		}
		else{
			return get_op(_get(l,r,b,(b+u)/2,tree[now].left), _get(l,r,(b+u)/2,u,tree[now].right));
		}
	}

	T get_query(int l, int r, int version){
		int root=version_root[version];
		return _get(l,r,0,n,root);
	}
	

	virtual T update_op(T pre, T delta){
		return def;
	}

	virtual T get_op(T left, T right){
		return def;
	}
};


template<typename T>
vector<T> comvol(vector<T> A, vector<T> B){
	
};

//-----------------------ここまでライブラリ-----------------------------//


int main(){
	//// おまじない /////
	//ios_base::sync_with_stdio(false);
	//cin.tie(nullptr);
	/////////////////////

	int D;
	cin>>D;
	cout<<"? 0\n";
	int a;
	cin>>a;
	cout<<"? 1\n";
	int b;
	cin>>b;
	cout<<"! "<<b-a<<"\n";
}