#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")//火车头优化
#include <bits/stdc++.h>
#define pi acos(-1)
#define m 19260817//hash
#define int _in128//扩范围
using namespace std;
template<typename T> void read(T &x) {
	int f = 1;
	x = 0;
	char c = getchar();
	while (!isdigit(c)) {
		if (c == '-') f = -1;
		c = getchar();
	}
	while (isdigit(c)) {
		x = x * 10 + c - '0';
		c = getchar();
	}
	x = x * f;
}//快读
void floyd(int n){
	for (int k = 0; k <= n; ++k)
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= n; ++j){
				if (k == 0)
				   dp[k][i][j] = g[i][j];
				else
					dp[k][i][j] = min(dp[k - 1][i][j], dp[k - 1][i][k] + dp[k - 1][k][j]);
			}
}//floyd------最短路
void dijkstra(int n){
	for (int i = 1; i <= n; ++i){
		int mind = inf;
		int v = 0;
		for (int j = 1; j <= n; ++j)
			if (!vis[j] && d[j] < mind){
				mind = d[j];
				v = j;
			}
		if (mind == inf)
		   break;
		vis[v] = true;
		for (int j = 0; j < g[v].size(); ++j)
			d[g[v][j].v] = min(d[g[v][j].v], d[v] + g[v][j].w);
	}
}//dijkstra------单源最短路
-void write(int x)-{
	if(x < 0)
		x = ~x + 1, putchar('-');
	if(x > 9)
		write(x / 10);
	putchar(x % 10 + '0');
}//快输
void spfa(int s)
{
	queue<int> q;
	q.push(s);
	int dis[N];
	for(int i = 1; i <= n; ++i)
		dis[i] = 1e9;
	dis[s] = 0;
	while(q.size()){
		u = q.front();
		q.pop();
		vis[u] = 0;
		for(int i = head[u]; i > 0; i = e[i].next){
			v = e[i].v;
			if(dis[v] > dis[u] + e[i].d){
				dis[v] = dis[u] + e[i].d;
				if(!vis[v]){
					q.push(v);
					vis[v] = 1;
				}
			}
		}
	}
	return;
}//spfa------单源最短路
inline int getnxt(char *s, int m, int *nxt){
	nxt[1] = 0;
	for (int i = 2; i <= m; ++i){
		int &j = nxt[i];
		j = nxt[i - 1];
		while(j && s[j + 1] !=s [i])
	 	    j = nxt[j];
		if(s[j + 1] == s[i])
            j++;
	}
	return 0;
}//接下个函数
inline int KMP(char *t, int n, char *s, int m, int *nxt, int *pos)
{
	int k = 0;
	for(int i = 1, j = 0; i <= n; i++){
		while(j && s[j + 1] != t[i])
	        j = nxt[j];
		if(j < m &&s[j + 1] == t[i]) j++;
		if(j == m){
			++k;
			pos[k] = i - m + 1;
			j = nxt[j];
		}
	}
	return k;
}//KMP树
int lca(int u, int v){
	if(dep[u] < dep[v]) swap(u, v);
	for(int i = 20; i >= 0; --i)
		if(dep[f[u][i]] >= dep[v])
			u = f[u][i];
	if(u == v)
		return u;
	for(int i = 20; i >= 0; --i)
		if(f[u][i] != f[v][i]){
			u = f[u][i];
			v = f[v][i];
		}	
	return f[u][0];
}//lca
void tarjan(int u){
	s.push(u);
	dfn[u] = low[u] = ++tt;
	vis[u ]= 1;
	for(int i = head[u]; i > 0; i = e[i].next){
		int v = e[i].to;
		if(!dfn[v]){
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if(vis[v])
			low[u] = min(low[u], low[v]);
	}
	if(dfn[u] == low[u]){
		int now;
		do
		{
			now = s.top();
			vis[now] = 0;
			s.pop();
			sd[now] =u ;
			if(now == u)
				break;
			num[u] += num[now];
		}while(now != u);
	}
	return;
}//tarjan------强连通分量
long long quickpower(long long x, long long k){
	long long s = 1;
	while(k){
    	if(k & 1){
    		s *= x;
			s %= z;
		}	
       	x *= x;
        x %= z;
       	k >>= 1;
    }
    return s % z;
}//快速幂
void highplus(string a1, string b1){
	int lena = strlen(a1);
    int lenb = strlen(b1);
    for (int i = 0; i < lena; ++i) a [lena - i] = a1[i] - 48;
    for (int i = 0; i < lenb; ++i) b [lenb - i] = b1[i] - 48;
    int lenc = 1 ;
    while (lenc <= lena || lenc <= lenb){
        c [lenc] = a[lenc] + b [lenc] + x;
        x = c[lenc] / 10;
        c [lenc] %= 10;
        ++lenc;
    }
    c[lenc] = x;
    if (c[lenc] == 0) --lenc;
    for (int i = lenc; i >= 1; --i) cout << c[i];
}//高精度加法
void highminus(string a1, string a2){
	int lena = strlen(n1), lenb = strlen(n2) ;
    if (lena < lenb || (lena == lenb && strcmp(n1, n2) < 0)){
        strcpy(n, n1);
        strcpy(n1, n2);
        strcpy(n2, n);
        swap(lena, lenb);
        printf("-");
    }
    for (int i = 0; i < lena; ++i) a[lena - i] = int(n1[i] - '0');
    for (int i = 0; i < lenb; ++i) b[lenb - i] = int(n2[i] - '0');
    int i = 1;
    while (i <= lena || i <= lenb){
        if (a[i] < b[i]){
            a[i] += 10;
            a[i + 1]--;
        }
        c[i] = a[i] - b[i];
        ++i;
    }
    int lenc = i;
    while (c[lenc] == 0 && lenc > 1) --lenc;
    for (int i = lenc; i >= 1 ; --i) cout << c[i];
}//高精度减法
void hightimes(string a1, string s2){
    int lena = strlen(a1), lenb = strlen(b1);
    for(int i = 0; i < lena; ++i) a[lena - i] = a1[i] - 48;
    for(int i = 0; i < lenb; ++i) b[lenb - i] = b1[i] - 48;
    for(int i = 0; i <= lena; ++i){
        x = 0;
        for (int j = 1; j <= lenb; ++j){
            c[i + j - 1] += a[i] * b[j] + x;
            x = c[i + j - 1] / 10 ;
            c[i + j - 1] %= 10 ;
        }
        c[i + lenb] = x ;
    }
    int lenc = lena + lenb;
    while (c[lenc] == 0 && lenc > 1) lenc--;
    for (int i = lenc; i > 0 ; --i) cout << c[i];
}//高精度乘法
void highdiv(string a1, string a2){
	int la = a[1].size();
    for(int i = 0; i < la; ++i)
        a[la - i - 1] = str[i] - '0';
    int x = 0;
    for(i = la - 1; i >= 0; --i) {
        c[i] = (x * 10 + a[i]) / b;
        x = (x * 10 + a[i]) % b;
    }
    lc = la;
    while(lc > 1 && c[lc - 1] == 0)
        lc--;
    for(i = 0; i < lc; i++)
        cout << c[lc - i - 1];
    cout << " " << x << endl;
}//高精度除法
signed main(){//扩大范围
	ios::sync_with_stdio(false);//加快cin
flag:
	 //做点什么
	 if (/*整些判断条件*/) goto flag;
	 while (left + 1 < right){
	 	int mid = (l + r) / 2;
		//在这里判断
		if(/*大了*/) r = mid - 1;
		else l = mid + 1
	 }//二分模板
}