제출 #106031

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
106031		OpenTheWindow	Gap (APIO16_gap)	C++14	컴파일 에러	0 ms	0 KiB

gap

#include<iostream>
#include<string>
#include<set>
#include<utility>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>
#include<stack>

#include<bits/stdc++.h>

#include"gap.h"

using namespace std;


long long findGap(int T, int N){
	long long ans = 0;

	if(T == 1){
		vector<long long> a;

		long long s = 0, t = 1000000000000000000LL;
		while (true)
		{
			long long mn, mx;

			if(s > t) break;
			MinMax(s, t, &mn, &mx);

			if(mn == -1) break;

			if(mn < mx){
				a.push_back(mn);
				a.push_back(mx);

				s = mn + 1;
				t = mx - 1;
			}
			if(mn == mx){
				a.push_back(mn);
				break;
			}
		}

		assert(a.size() == N):

		sort(a.begin(), a.end());

		for(int i=0; i<N-1; i++){
			ans = max(ans, a[i+1] - a[i]);
		}


	}

	return ans;
}


//using namespace std;

/*
int dp[3001][3001] = {};
	
int main(){
	string s, t;

	cin >> s >> t;


	for(int i=1; i<=s.size(); i++){
		for(int j=1; j<=t.size(); j++){
			if(s[i-1] == t[j-1]){
				dp[i][j] = dp[i-1][j-1] + 1;
			}
			else{
				if(dp[i][j-1] < dp[i-1][j]){
					dp[i][j] = dp[i-1][j];
				}
				else if(dp[i][j-1] < dp[i-1][j]){
					dp[i][j] = dp[i][j-1];
				}
			}
		}
	}

	string ans;
	int li = s.size()+1, lj = t.size()+1;
	for(int i=s.size(); i>=0; i--){
		for(int j=t.size(); j>=0; j--){
			if(dp[i][j] == dp[i-1][j]){

			}
			else if(dp[i][j] == dp[i][j-1]){

			}
		}
	}
	

	reverse(ans.begin(), ans.end());

	if(ans.size() == 0){
		cout << " " << endl;
	}
	else{
		cout << ans << endl;
	}

	return 0;
}
*/

/*

if(dp[i][j] > dp[i-1][j-1] && dp[i-1][j-1] == dp[i][j-1] && dp[i-1][j-1] == dp[i-1][j]){
				
				if(i<=li && j<=lj){
					ans += s[i-1];
					
					li = i;
					lj = j;
				}

			}

int main(){
	int N;
	cin >> N;

	cout << N%11 << endl;
}
*/

/*
int main(){
	int N;
	cin >> N;

	int ans = 0;
	for(int i=0;; i++){

		ans = i;
		if(i*i > N){
			ans--;
			break;
		}

	}

	cout << ans << endl;

	return 0;
}
*/


/*
int main(){
	string s;
	cin >> s;

	for(int i=1; i<=s.size(); i++){
		cout << i << endl;
	}


	return 0;
}
*/

/*
int N, W;
int w[100], v[100];
int dp[100][1000];

int solve(int now, int m){
	if(now == N) return 0;


}

int main(){
	cin >> N >> W;
	for(int i=0; i<N ; i++){
		cin >> w[i] >> v[i];
	}



	return 0;
}
*/

/*
vector<char> seg;
int K, n, size;



void update(int i, char x){
	i += n-1;
	seg[i] = x;

	while(i>0){
		i = (n-1)/2;
		seg[i] = min(seg[2*i+1], seg[2*i+2]);
	}
}

int smaller(int a, int now, int l, int r){
	int b = a + K;

	if(r <= a || b <= l) return 0;
	if(a <= l && r <= b){
		if(seg[a] < seg[now]){
			int tmp = now;
			while (tmp >= n - 1)
			{
				tmp = 2*now + 1;
				if(seg[tmp] == seg[now]){}
				if(seg[tmp+1] == seg[now]) tmp++;
			}

			return tmp;
		}
	}
	else{
		int a1 = smaller(a, 2*now+1, l, (l+r)/2);
		int a2 = smaller(a, 2*now+1, (l+r)/2, r);

		if(seg[a] < seg[a1]){
			if(seg[a1] < seg[a2]){
				return a2;
			}
			else{
				return a1;
			}
		}

	}
}

int main(){
	string s;
	cin >> s >> K;

	size = 1;
	while (size < s.size())
	{
		size *= 2;
	}
	size = 2*size - 1;

	n = (1+size)/2;


	for(int i=0; i<size; i++){
		seg.push_back('z');
	}

	for(int i=0; i<s.size(); i++){
		update(i, s[i]);
	}

	int now = 0;
	while (K>0)
	{
		int tmp = smaller(now, 0, 0, n);
	}



	return 0;
}
*/

/*
int N, q;
vector<int> seg;
int segSize = 2;
int n;

void add(int x, int y){

	x += n - 1;
	seg[x] += y;

	while(x > 0){
		x = (x-1)/2;
		seg[x] = seg[2*x+1] + seg[2*x+2];
	}
	
}

int sum(int a, int b, int k, int l, int r){
	if(r <= a || b <= l) return 0;
	if(a <= l && r <= b){
		return seg[k];
	}
	else{
		return sum(a, b, 2*k+1, l, (l+r)/2 ) + sum(a, b, 2*k+2, (l+r)/2, r);
	}
}

int main(){

	cin >> N >> q;

	

	while(segSize < N){
		segSize *= 2;
	}

	segSize *= 2;
	segSize--;

	n = (segSize+1)/2;

	for(int i=0; i<segSize; i++){
		seg.push_back(0);
	}

	for(int i=0; i<q; i++){
		int com, x, y;
		cin >> com >> x >> y;

		if(com == 0){
			add(x-1, y);
		}

		if(com == 1){
			cout << sum(x-1, y, 0, 0, n) << endl;
		}
	}


	return 0;
}
*/

/*
long long K, A, B;
long long ans = 0;
int main() {
	cin >> K >> A >> B;
 
 
	if (A + 1 < B) {
		
		if (K + 1 > A + 1) {
			ans += B;
			K -= A + 1;
 
			ans += K / (A + 2) * B;
			ans += K % (A + 2);
		}
 
		
	}
	else {
		ans = K + 1;
	}
 
	cout << ans << endl;
 
 
	return 0;
}
*/


/*
int N, W;
long long w[100], v[100] = {};
long long dp[101][100100];

int main(){

	cin >> N >> W;
	for(int i=0; i<=N; i++){
		if(i<N)
			cin >> w[i] >> v[i];

		for(int j=0; j<=100000; j++){
			dp[i][j] = 99999999999LL;
		}
	}

	for(int i=0; i<=N; i++){
		dp[i][0] = 0;
	}

	
	for(int i=1; i<=N; i++){
		for(int j=1; j<=100000; j++){

			dp[i][j] = j-v[i-1] < 0 ? dp[i-1][j] : min(dp[i-1][j], dp[i-1][j-v[i-1]] + w[i-1]);

		}
	}

	int ans = 0;
	for(int i=0; i<=100000; i++){
			if(dp[N][i] <= W){
				ans = max(ans, i);
			}
	}



	cout << ans << endl;

	
	for(int i=1; i<=N; i++){
		for(int j=1; j<=100*N; j++){

			cout << dp[i][j] << " ";

		}
		cout << endl;
	}
	

	return 0;
}
*/

/*
int N, W;
long long w[111], v[111];
long long dp[111][111111];

long long solve(int now, int m){
	if(m > W) return -999999999999;

	if(now == N) return 0;

	if(dp[now][m] != -1) return dp[now][m];
	
	dp[now][m] = max(solve(now+1, m), solve(now+1, m + w[now]) + v[now]);
	return dp[now][m];
}

int main(){

	cin >> N >> W;
	for(int i=0; i<N; i++){
		cin >> w[i] >> v[i];

		for(int j=0; j<W; j++){
			dp[i][j] = -1;
		}
	}

	cout << solve(0, 0) << endl;


	return 0;
}
*/

/*
int N;
int ABC[100001][3] = {};
int dp[100001][3];

int solve(int now, int m){
	if(now == N+1) return 0;

	if(dp[now][m] != -1) return dp[now][m];

	dp[now][m] = max(solve(now + 1, (m+1)%3) + ABC[now][(m+1)%3], solve(now + 1, (m+2)%3) + ABC[now][(m+2)%3]);
	return dp[now][m];
}

int main(){
	cin >> N;
	for(int i=1; i<=N; i++){
		cin >> ABC[i][0] >> ABC[i][1] >> ABC[i][2];
	}

	for(int i=0; i<=N; i++){
		for(int j=0; j<3; j++){
			dp[i][j] = -1;
		}
	}

	cout << solve(0, 0) << endl;

	return 0;
}
*/

/*
int N, K;
int h[100000];
int dp[100000];

int solve(int now){
	if(now == N-1) return 0;

	if(now >= N-1){
		return 9999999999;
	}

	if(dp[now] != -1) return dp[now];

	int tmp = 9999999999;
	for(int i=1; i<=K; i++){
		tmp = min(abs(h[now+i] - h[now]) + solve(now+i), tmp);
	}
	dp[now] = tmp;
	return dp[now];
}

int main(){
	cin >> N >> K;
	for(int i=0; i<N; i++){
		cin >> h[i];

		dp[i] = -1;
	}


	cout << solve(0) << endl;

	return 0; 
}
*/


/*
int N;
int h[100000];
int dp[100000];

int solve(int now){
	if(now == N-1) return 0;

	if(dp[now] != -1) return dp[now];

	if(now == N-2){
		dp[now] = abs(h[now+1] - h[now]) + solve(now+1);
	}
	else{
		dp[now] = min(abs(h[now+1] - h[now]) + solve(now+1), abs(h[now+2] - h[now]) + solve(now+2));
	}

	return dp[now];
}
int main(){
	cin >> N;
	for(int i=0; i<N; i++){
		cin >> h[i];

		dp[i] = -1;
	}

	cout << solve(0) << endl;

	return 0;
}
*/

/*
int D, N;
int T[200], A[200], B[200], C[200];
int dp[100][100];

int solve(int now, int m){ //now:日数 m:派手さの差の絶対値の合計
	if(now == N) return 0;

	if(dp[now][m] 
}

int main(){
	cin >> D >> N;

	for(int i=0; i<D; i++){
		cin >> T[i];
	}

	for(int i=0; i<N; i++){
		cin >> A[i] >> B[i] >> C[i];
	}

	


	return 0;
}
*/

/*
//6
int N;
int A[100];
int dp[100][200];

int solve(int now, int m, int B[100]){
	if(now == N){
		return 1;
	}

	dp[now][m] = 0;

	for(int i=0; i<N; i++){
		if(B[i]>0 && i != m-1 && i != m && i != m+1){
			B[i]--;
			dp[now][m] += solve(now+1, i, B);
			B[i]++;
		}
	}
	dp[now][m] %=  10007 ;

	return dp[now][m];
}

int main(){
	cin >> N;
	for(int i=0; i<N; i++){
		cin >> A[i];

		for(int j=0; j<200; j++){
			dp[i][j] = -1;
		}
	}

	cout << solve(0, 200, A);

	return 0;
}
*/

/*
//5
int N, M;
int A[200000], l[200000], r[200000];
vector<int> max1[200000] = {};
int tmp[4000][3] = {};
int ok[200000] = {};
int main(){
	cin >> N >> M;

	for(int i=0; i<N; i++){
		cin >> A[i];
	}

	for(int i=0; i<M; i++){
		cin >> l[i] >> r[i];
		l[i]--;
		r[i]--;

		for(int j = l[i]; j<=r[i]; j++){
			ok[j]++;
		}
	}


	tmp[0][0] = tmp[0][1] = 0;
	for(int i=1; i<=N; i++){
		if(ok[i-1] == 0){
			tmp[i][0] += A[i-1] + tmp[i-1][1] + tmp[i-1][2];
			tmp[i][1] = tmp[i][0];
		}
		else if(ok[i-1] == 1){
			tmp[i][1] += max(A[i-1] + tmp[i-1][0], tmp[i-1][1]);
			tmp[i][0] = tmp[i-1][0];
		}
		else if(ok[i-1] == 2){
			tmp[i][1] = tmp[i-1][1];
			tmp[i][2] = max(tmp[i-1][1], tmp[i-1][2]);
		}
	}

	cout << tmp[N][0] << endl;


	return 0;
}
*/


//4
/*
int N;
int A[100000];
int main(){
	cin >> N;

	vector<int> x, y, z; //xは頂、ｙは谷、ｚは合わせたやつ

	cin >> A[0];

	int B[100001];
	B[0] = 0;
	for(int i=1; i<N; i++){
		cin >> A[i];

		B[i] = A[i] - A[i-1];

		if(B[i-1] * B[i] < 0){
			if(B[i-1] > 0){
				x.push_back(A[i-1]);
				z.push_back(A[i-1]);
			}
			else if(B[i-1] < 0){
				y.push_back(A[i-1]);
				z.push_back(A[i-1]);
			}
		}
		else if(B[i] == 0){
			if(B[i-1] > 0){
				x.push_back(A[i-1]);
				z.push_back(A[i-1]);
			}
			else if(B[i-1] < 0){
				y.push_back(A[i-1]);
				z.push_back(A[i-1]);
			}
		}	
	}

	if(B[1] < 0){
		x.push_back(A[0]);
		z.push_back(A[0]);
	}

	if(B[N-1] > 0){
		x.push_back(A[N-1]);
		z.push_back(A[N-1]);
	}
	

	sort(x.begin(), x.end());
	sort(y.begin(), y.end());
	sort(z.begin(), z.end());

	if(y[0] == A[N-1]) y.erase(y.begin());

	reverse(x.begin(), x.end());
	reverse(y.begin(), y.end());
	reverse(z.begin(), z.end());


	int xi = 0, yi = 0;
	int tmp = 0;
	int ans = 0;
	for(int i=0; i<z.size(); i++){
		if(z[i] == y[yi]){
			tmp--;
			yi++;

			if(yi >= y.size()) yi--;
		}
		else if(z[i] == x[xi]){
			tmp++;
			xi++;

			if(xi >= x.size()) xi--;
		}

		ans = max(ans, tmp);
	}


	cout << ans << endl;

		


	return 0;
}
*/

/*
//3
int N;
string s;
int main(){
	cin >> N >> s;

	int ans = 0;
	for(int i=1; i<N; i++){
		if(s[i-1] != s[i]){
			ans++;
			i++;
		}
	}

	cout << ans << endl;


	return 0;
}
*/

/*
//2
int main(){
	int N, M;
	int X[100];

	cin >> N;
	for(int i=0; i<N; i++){
		cin >> X[i];
	}

	cin >> M;
	for(int i=0; i<M; i++){
		int a;
		cin >> a;
		a--;

		for(int j = 0; j<N; j++){
			if(X[a] + 1 == X[j]){
				break;
			}
			else if(j == N -1){
				X[a]++;
			}
		}
		
		if(X[a] > 2019) X[a] = 2019;
	}

	for(int i=0; i<N; i++){
		cout << X[i] << endl;
	}

	return 0;
}
*/

/*
//1
int main(){
	int a, b, c;
	cin >> a >> b >> c;

	int week = c/(7*a+b);

	int tmp = c%(7*a+b);

	int ans = tmp/a;

	if(tmp%a != 0) ans++;

	cout << min(ans + 7*week, 7*(week+1) ) << endl;


	return 0;
}
*/

/*
int N;
int x[3000], y[3000];

int main(){
	cin >> N;
	for(int i=0; i<N; i++){
		cin >> x[i] >> y[i];
	}


	for(int i=0; i<N; i++){
		for(int j=i+1; j<N; j++){
			for(int k=j+1; k<N; k++){
				for(int l=k+1; l<0; l++){
					int wide = max(abs(x[i]-x[j]), max(abs(x[i]-x[k]), max(abs(x[i] - x[l]), max(abs(x[j]-x[k]), max(abs(x[j] - x[l]), abs(x[k]-x[l])))))); 
					int height = max(abs(y[i]-y[j]), max(abs(y[i]-y[k]), max(abs(y[i] - y[l]), max(abs(y[j]-y[k]), max(abs(y[j] -y[l]), abs(y[k]-y[l])))))); 
					if(wide == height){

					}
				}
			}
		}
	}


	return 0;
}
*/

//最長の階段
/*
int N, k;
int num[100000];
bool empty = false;
int sizes[100000][2] = {};
int main(){
	cin >> N >> k;
	for(int i=0; i<k; i++){
		int tmp;
		cin >> tmp;

		if(tmp==0) empty = true;
		else num[i] = tmp;
	}

	sort(num, num+k);

	sizes[0][0] = 0;
	for(int i=1; i<=k; i++){
		int x = num[i] - num[i-1];
		
		if(x == 1){
			sizes[i][0] = sizes[i-1][0] + 1;
			sizes[i][1] = sizes[i-1][1] + 1;
		}
		else if(x == 2 && empty == true){
			sizes[i][1] = sizes[i-1][0] + 2;
		}
		else{
			sizes[i][0] = 0;
			sizes[i][1] = 0;
		}
	}

	int ans = 0;
	for(int i=0; i<k; i++){
		for(int j=0; j<2; j++){
			ans = max(ans, sizes[i][j]);
		}
	}

	cout << ans+1 << endl;
	
	return 0;
}
*/

/*
int N, F;
vector<string> sets[100];
set<string> items;
vector<pair<string, string>> pairs;
int main(){
	cin >> N >> F;

	for(int i=0; i<N; i++){
		int m; 
		cin >> m;
		for(int j=0; j<m; j++){
			string tmp;
			cin >> tmp;
			sets[i].push_back(tmp);
			items.insert(tmp);
		}
	}

	vector<string> kind;
	for(auto itr = items.begin(); itr != items.end(); itr++){
		kind.push_back(*itr);
	}

	for(auto i=0; i<kind.size(); i++){
		for(auto j=1+i; j<kind.size(); j++){
			for(int k=0; k<N; k++){
				int ok1 = 0;
				for(int l=0; l<sets[k].size(); l++){
					if(kind[i] == sets[k][l]){
						ok1++;
					}
					if(kind[j] == sets[k][l]){
						ok1++;
					}
				}
				if(ok1 == 2){
					pairs.push_back(make_pair(kind[i], kind[j]));
				}
			}
		}
	}

	set<pair<string, string>> ans;
	for(int i=0; i<pairs.size(); i++){
		int tmp = 0;
		for(int j=i++; j<pairs.size(); j++){
			if(pairs[i] == pairs[j]){
				tmp++;
			}
		}
		if(tmp>=F){
			ans.insert(pairs[i]);
		}
	}

	cout << ans.size() << endl;
	for(auto i=ans.begin(); i!=ans.end(); i++){
		pair<string, string> tmp = *i;
		cout << tmp.first << " " << tmp.second << endl;
	}

	return 0;
}
*/

/*
int h[10], w[10];
vector<int> sh, sw;

int main(){

	bool ok = true;
	for(int i=0; i<6; i++){
		int htmp, wtmp;
		cin >> htmp >> wtmp;

		if(htmp < wtmp){
			h[i] = htmp;
			w[i] = wtmp;
		}
		else{
			h[i] = wtmp;
			w[i] = htmp;
		}
	}

	for(int i=0; i<5; i++){
		for(int j=i+1; j<6; j++){
			if(h[i] == h[j] && w[i] == w[j] && h[i]>0){
				sh.push_back(h[i]);
				sw.push_back(w[i]);
				h[i] = h[j] = w[i] = w[j] = -1;
				break;
			}
		}
	}

	if(sw.size() != 3){
		ok = false;
		cout << "no" << endl;
	}


	for(int i=0; i<2; i++){
		for(int j=i+1; j<3; j++){
			if(sh[i] == sh[j] && sh[i] != -1){
				sh[i] = sh[j] = -1;
			}
			else if(sh[i] == sw[j] && sh[i] != -1){
				sh[i] = sw[j] = -1;
			}
			else if(sw[i] == sh[j] && sw[i] != -1){
				sw[i] = sh[j] = -1;
			}
			else if(sw[i] == sw[j] && sw[i] != -1){
				sw[i] = sw[j] = -1;
			}
			else if(j == 2){
				ok = false;
				cout << "no" << endl;
			}
		}
	}


	if(ok) cout << "yes" << endl;



	return 0;
}
*/

/*
int N;
int lc[100], rc[100], p[100], dp[100];
int root; 
vector<int> leaves;

int dpth(int now){
	if(now == root) return 0;

	return dpth( p[now] ) + 1;
}

int hgt(int now){
	for(int i=0; i<leaves.size(); i++){
		if(now == leaves[i]) return 0;
	}

	if(dp[now] != -1) return dp[now];
	dp[now] = (max(hgt(lc[now]), hgt(rc[now])) + 1);

	return dp[now];
}

void print(int id){
	cout << "node " << id << ": ";
	cout << "parent = " << p[id] << ", ";

	cout << "sibling = ";
	if(p[id] == -1) cout << -1;
	else if(lc[ p[id] ] != id) cout << lc[ p[id] ];
	else if(rc[ p[id] ] != id) cout << rc[ p[id] ];
	else cout << -1;
	cout << ", ";

	cout << "degree = ";
	int tmp = 0;
	if(lc[id] != -1) tmp++;
	if(rc[id] != -1) tmp++;
	cout << tmp << ", ";

	cout << "depth = " << dpth(id) << ", ";

	cout << "height = " << hgt(id) << ", ";

	if(p[id] == -1) cout << "root";
	else if(lc[id] == -1 && rc[id] == -1) cout << "leaf";
	else cout << "internal node";

	cout << endl;
}

int main(){
	cin >> N;

	for(int i=0; i<N; i++){
		lc[i] = rc[i] = p[i] = dp[i] = -1;
	}

	for(int i=0; i<N; i++){
		int id, left, right;
		cin >> id >> left >> right;

		lc[id] = left;
		rc[id] = right;
		p[left] = id;
		p[right] = id;
	}



	for(int i=0; i<N; i++){
		if(p[i] == -1) root = i;
		if(lc[i] == -1 && rc[i] == -1) leaves.push_back(i);
	}	

	for(int i=0; i<N; i++){
		print(i);
	}


	return 0;
}
*/

/*
int N;
int parent[100000], Left[100000], Right[100000];
int d[100000];

void rec(int u, int p){
	d[u] = p;
	if(Right[u] != -1) rec(Right[u], p);
	if(Left[u] != -1) rec(Left[u], p+1);
}

void print(int n){
	cout << "node " << n;
	cout << ": parent = "<< parent[n];
	cout << ", depth = "<< d[n] << ", ";
	
	if(parent[n] == -1) cout << "root";
	else if(Left[n] == -1) cout << "leaf";
	else cout << "internal node";

	cout << ", [";

	int c = Left[n];
	for(int i=0; c != -1; i++){
		if(i) cout << ", ";
		cout << c;
		c = Right[c];
	}
	cout << "]" << endl;
}

int main(){
	cin >> N;
	for(int i=0; i<N; i++){
		parent[i] = Left[i] = Right[i] = -1;
	}

	for(int i=0; i<N; i++){
		int id, k, l;
		cin >> id >> k;
		for(int j=0; j<k; j++){
			int c;
			cin >> c;
			if(j == 0){
				Left[id] = c;
			}
			else{
				Right[l] = c;
			}
			l = c;
			parent[c] = id;
		}
	}

	int r;
	for(int i=0; i<N; i++){
		if(parent[i] == -1) r = i;
	}

	rec(r, 0);
	
	for(int i=0; i<N; i++) print(i);

	return 0;
}
*/

//カードゲーム
/*
int main(){
	int N;
	cin >> N;
	vector<int> Taro, Hana;

	for(int i=0; i<N; i++){
		int tmp;
		cin >> tmp;
		Taro.push_back(tmp);
	}
	sort(Taro.begin(), Taro.end());

	for(int i=1; i<=2*N; i++){
		for(int j=0; j<N; j++){
			if(i == Taro[j]){
				break;
			}
			else if(j = N-1){
				Hana.push_back(i);
			}
		}
	}

	int TaroSize = Taro.size();
	int HanaSize = Hana.size();

	bool taroturn = true;
	int now = 0;
	while(TaroSize != 0 && HanaSize != 0){
		if(taroturn){
			for(int i=0; i<TaroSize; i++){
				if(now < Taro[i]){
					now = Taro[i];
					taroturn = false;
				}
			}
		}
		else{

		}
	}

	return 0;
}
*/

//サッカー
/*
int main(){
	int N;
	cin >> N;
	
	int X[4][3] = {};

	for(int i=0; i<N*(N-1)/2; i++){
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		a--; 
		b--;

		if(c>d){
			X[a][0]++;
			X[b][1]++;
		}
		if(c == d){
			X[a][2]++;
			X[b][2]++;
		}
		if(c<d){
			X[a][0]++;
			X[b][1]++;
		}
	}


	return 0;
}
*/

//すごろく
/*
int main(){
	int N, M;
	cin >> N >> M;
	
	int Place[1000];
	for(int i=0; i<N; i++){
		cin >> Place[i];
	}

	int ans;
	int now = 0;
	for(int i=0; i<M; i++){
		int sai;
		cin >> sai;

		now += sai;
		now += Place[now];

		if(now >= N-1){
			ans = i + 1;
			break;
		}
	}

	cout << ans << endl;

	return 0;
}
*/

//鉛筆
/*
int main(){
	int N, a, b, c, d;
	cin >>  N >> a >> b >> c >> d;
	/*
	int x, y;
	for(int i=1; i*a < N; i++){
		x = i*b;
	}
	for(int i=1; i*c < N; i++){
		y = i*d;
	}

	x += b;
	y += d;*/
	
	/*
	int x = N/a * b;
	if(N%a != 0) x += b;

	int y = N/c * d;
	if(N%c != 0) y += d;
	

	if(x>y) x = y;

	cout << x << endl;

	return 0;
}
*/

/*
int main(){
	int a, b, c, d, e;
	cin >> a >> b >> c >> d >> e;

	int ans = 0;

	if(a<0){
		ans += c * abs(a) + d;
		a = 0;
	}
	
	ans += (b-a)*e;

	cout << ans << endl;

	return 0;
}
*/

/*
//科目選択
int main(){
	int a, b, c, d, e, f;
	cin >> a >> b >> c >> d >> e >> f;

	if(e < f) e = f;

	int sum = a + b + c + d;

	if(a>b) a = b;
	if(a>c) a = c;
	if(a>d) a = d;

	cout << sum - a + e << endl;

	return 0;
}
*/

//最大の和
/*
int main(){
	while(true){
		int k;
		int A[100000];
		int N;

		cin >> N >> k;
		if(N == 0 && k == 0) break;

		A[0] = 0;
		for(int i=1; i<=N; i++){
			cin >> A[i];
			A[i] = A[i] + A[i-1];
		}

		int ans = -99999999;
		for(int i=1; i+k-1<N; i++){
			ans = max(ans, A[i+k-1] - A[i-1]);
		}

		cout << ans << endl;
	}

	return 0;
}
*/
//フィボナッチ数列
/*
int dp[100];
int N;

int solve(int n){
	if(dp[n] != -1) return dp[n];

	dp[n] = solve(n-2) + solve(n-1);
	return dp[n];
}

int main(){
	cin >> N;

	for(int i=0; i<100; i++){
		dp[i] = -1;
	}
	dp[0] = 1;
	dp[1] = 1;

	cout << solve(N) << endl;

	return 0;
}
*/
/*
//Longest Common Subsequence
int c[1001][1001];

int lcs(string X, string Y){
	int m = X.size();
	int n = Y.size();
	int maxl = 0;

	X = ' ' + X;
	Y = ' ' + Y;

	for(int i=0; i<=m; i++){
		for(int j=0; j<=n; j++){
			c[i][j] = 0;
		}
	}

	//for(int i=1; i<=m; i++) c[i][0] = 0;
	//for(int i=1; i<=n; i++) c[0][i] = 0;

	for(int i=1; i<=m; i++){
		for(int j=1; j<=n; j++){
			if(X[i] == Y[j]){
				c[i][j] = c[i-1][j-1] + 1;
			}
			else{
				c[i][j] = max(c[i-1][j], c[i][j-1]);
			}
			maxl = max(c[i][j], maxl);
		}
	}

	return maxl;
}

int main(){
	int q;
	cin >> q;
	string X, Y;

	for(int i=0; i<q; i++){
		cin >> X >> Y;
		cout << lcs(X, Y) << endl;
	}

	return 0;
}


/*
int main(){

	/*
	int x,y;
	cin >> x >> y;

	cout << x << " + " << y << " = " << x+y << endl;
	cout << x << " - " << y << " = " << x-y << endl;
	cout << x << " * " << y << " = " << x*y << endl;
	cout << x << " / " << y << " = " << x/y << endl;
	cout << x << " % " << y << " = " << x%y << endl;
	*/

	/*
	int p;
	cin >> p;

	if(p<50){
		cout << "Your grade is C" << endl;
	}
	else if(p >= 50 && p < 70){
		cout << "Your grade is B" << endl;
	}
	else if(p >= 70 && p<100){
		cout << "Your grade is A" << endl;
	}
	else if(p == 100){
		cout << "Your grade is S" << endl;
	}
	*/

	/*
	string name;
	double a, b, c, d, f;
	cin >> name >> a >> b >> c >> d >> f;

	double p = (5*a + 4*b + c*3 + d*2 + f)/(a + b + c + d + f);

	cout << name << " ";

	if(p == 5) cout << "Great!" << endl;
	if(p >= 4&& p < 5) cout << "Very Good" << endl;
	if(p >= 3&& p < 4) cout << "Good!" << endl;
	if(p < 3) cout << "Poor!" << endl;
	*/

/*
	int aw, al, ah;
	int bw, bl, bh;
	int cw, cl, ch;
	int dw, dl, dh;
	int ew, el, eh;

	cin >> aw >> al >> ah;
	cin >> bw >> bl >> bh;
	cin >> cw >> cl >> ch;
	cin >> dw >> dl >> dh;
	cin >> ew >> el >> eh;

	int ap = aw - al;
	int bp = bw - bl;
	int cp = cw - cl;
	int ap = dl;w - al;
	int ap = aw - al;

	return 0;
}
*/


//総当り
/*
int N, M;
int A[100];
int dp[100][100];

int solve(int now, int m){
	if(m == 0) return 1;
	if(now >= N) return 0;

	if(dp[now][m] != -1) return dp[now][m];

	if(solve(now+1, m) == 1){
		dp[now][m] = 1;
	}
	else{
		dp[now][m] = solve(now+1, m-A[now]);
	}

	return dp[now][m];
}

int main(){
	cin >> N;
	for(int i=0; i<N; i++){
		cin >> A[i];
	}

	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			dp[i][j] = -1;
		}
	}

	int q;
	cin >> q;
	for(int i=0; i<q; i++){
		cin >> M;
		if(solve(0, M) == 1){
			cout << "yes" << endl;
		}
		else{
			cout << "no" << endl;
		}
	}

	return 0;
}
*/
//幅優先探索
/*
int N;
int M[101][101];
queue<int> que;
int cost[101];

void solve(int now){
	for(int i=0; i<N; i++){
		if(M[now][i] == 1){
			if(cost[i] == -1){
				cost[i] = cost[now] + 1;
				que.push(i);
			}
			else if(cost[now] + 1 < cost[i]){
				cost[i] = cost[now] + 1;
				que.push(i);
			}
		}
	}
}

int main(){
	cin >> N;
	for(int i=0; i<N; i++){
		int u, k;
		cin >> u >> k;
		for(int j=0; j<k; j++){
			int v;
			cin >> v;
			M[u-1][v-1] = 1;
		}
	}

	for(int i=0; i<N; i++){
		cost[i] = -1;
	}

	cost[0] = 0;
	que.push(0);
	while (!que.empty())
	{
		solve(que.front());
		que.pop();
	}

	for(int i=0; i<N; i++){
		cout << i+1 << " " << cost[i] << endl;
	}

	return 0;
}
*/
//深さ優先探索
/*
int N;
int M[101][101] = {};
int d[101] = {};
int f[101] = {};
int ct = 0;

void solve(int now){	
	if(d[now] == 0) d[now] = ct;
	for(int i=1; i<=N; i++){
		if(M[now][i] == 1 && d[i] == 0){
			ct++;
			solve(i);
		}
		if(i == N){
			ct++;
			f[now] = ct;
		}
	}
}

int main(){
	cin >> N;

	for(int i=1; i<=N; i++){
		M[0][i] = 1;
	}

	for(int i=0; i<N; i++){
		int u, k;
		cin >> u >> k;
		for(int j=0; j<k; j++){
			int v;
			cin >> v;
			M[u][v] = 1;
		}
	}

	solve(0);

	for(int i=1; i<=N; i++){
		cout << i << " " << d[i] << " " << f[i] << endl;
	}

	return 0;
}
*/

//グラフの表現
/*
int main(){
	int n;
	int M[101][101] = {};
	cin >> n;

	for(int i=0; i<n; i++){
		int u, k;
		cin >> u >> k;
		for(int j=0; j<k; j++){
			int v;
			cin >> v;
			M[u-1][v-1] = 1;
		}
	}

	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			cout << M[i][j];
			if(j != n-1){
				cout << " ";
			}
			else{
				cout << endl;
			}
		}
	}

	return 0;
}
*/
//二乗法
/*
int main(){
	long long m,n;
	int MOD = 1000000007;
	cin >> m >> n;
	long long ans = 1;
	while(n != 0){
		if(n%2 == 1){
			ans *= m;
			ans %= MOD;
		}
		n = n/2;
		m = m*m;
		m %= MOD;
	}
	cout << ans << endl;

	return 0;
}
*/

//カードゲーム
/*
int n;
bool T[100], H[100];
int Tnum = n, Hnum = n;

int main (){
	cin >> n;
	for(int i=0; i<2*n; i++){
		T[i] = false;
	}

	for(int i=0; i<n; i++){
		int a;
		cin >> a;
		T[a] = true;
	}
	for(int i=0; i<n; i++){
		if(!T[i]){
			H[i] = true;
		}
	}

	int now;
	bool turn = true;
	for(int i=0; i<n; i++){
		if(T[i]){
			now = i;
			T[i] = false;
			Tnum--;
			turn = false;
			break;
		}
	}
	while(Tnum > 0 || Hnum > 0){
		for(int i=0; i<n; i++){
			if(T[i]){
				now = i;
				T[i] = false;
				Tnum--;
				turn = false;
				break;
			}
			else if(H[i]){
				now = i;
				H[i] = false;
				Hnum--;
				turn = true;
				break;
			}
		}
	}
	

	return 0;
}
*/
/*
int A[100];
int B[100];	
int n;
int ansT, ansH;
int taro = n - 1, hana = n;

void solve(int c, bool b){
		if(taro == 0){
			ansT = hana;
			return;
		}
		if(hana == 0 ){
			ansH = taro;
			return;
		}
		if(b){
			for(int i=0; i<n; i++){
				if(c < B[i]){
					int a = B[i];
					B[i] = -1;
					hana--;
					solve( a, !b);
					return;
				}
				else if(i==n-1){
					taro++;
					solve(0 , !b);
				}
			}
		}
		else{
			for(int i=0; i<n; i++){
				if(c < A[i]){
					int a = B[i];
					A[i] = -1;
					taro--;
					solve( a, !b);
					return;
				}
				else if(i==n-1){
					taro++;
					solve(0, !b);
				}
		}
	}
}
int main(){
	while(true){
		cin >> n;
		if(n == 0){
			break;
		}

		for(int i=0; i<n; i++){
			cin >> A[i];
		}
		sort(A, A+n);

		int m = 0;
		for(int i=0; i<n ; i++){
			for(int j=B[m]+1; j<=2*n; j++){
				if(A[i] != j){
					B[m] = j;
					m++;
				}
			}
		}

		solve(A[0], true);

		cout << ansT << endl << ansH << endl;
	}
	return 0;
}
*/

//最高のピザ
/*
int n,a,b,c;
int A[110];
int dp[110][110];

int main(){
	cin >> n >> a >> b >> c;

	for(int i=1; i<=n; i++){
		cin >> A[i];
	}

	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + A[i]);
		}
	}

	int ans = c/a;
	for(int i=0; i<=n; i++){
		ans = max(ans, (dp[n][i]+c)/(a + b*i) );
	}

	cout << ans << endl;

	return 0;
}
*/
	/*
	int x = 0;
	dp[0].first = 0;

	for(int j=0; j<n; j++){
		//X.push_back(temp);
		if(dp[j].first < dp[j].first + A[j]){
			dp[j+1].first = dp[j].first + A[j];
			dp[j+1].second = x;
		}
		else{
			dp[j+1] = dp[j];
		}
		//dp.push_back(-1);
	}

	int ans = 0;
	for(int i=0; i<n+1; i++){
		ans = max( (dp[i].first + c)/(dp[i].second * b + a), ans);
	}

	cout << ans << endl;
	*/
	//cout << solve(0) << endl;

//チーズ
/*
int h,w,n;
pair<int,int> factory[10];
int cost[1000][1000];
queue< pair<int,int> > que;
string S[1000];
int A[2][4] = {{-1, 1 ,0, 0}, {0, 0, -1, 1}};

void Solve(pair<int,int> Now){
	for(int i = 0; i<4; i++){
		int x = Now.first + A[0][i];
		int y = Now.second + A[1][i];
		if(x >= 0 && x < h&&y >= 0&&y < w && S[Now.first + A[0][i]][Now.second + A[1][i]] != 'X'){
			if(cost[Now.first][Now.second] + 1 < cost[x ][y]){
				 cost[x][y] = cost[Now.first][Now.second] + 1;
				 que.push(make_pair(x, y));
			}
		}
	}
	
	
	//上
	if(Now.first - 1 >= 0 && S[Now.first - 1][Now.second] != 'X'){
		if(cost[Now.first][Now.second] + 1 < cost[Now.first - 1][Now.second]){
			 cost[Now.first - 1][Now.second] = cost[Now.first][Now.second] + 1;
			 que.push(make_pair(Now.first -1, Now.second));
		}
	}
	//下
	if(Now.first + 1 < h && S[Now.first + 1][Now.second] != 'X'){
		if(cost[Now.first][Now.second] + 1 < cost[Now.first + 1][Now.second]){
			 cost[Now.first + 1][Now.second] = cost[Now.first][Now.second] + 1;
			 que.push(make_pair(Now.first + 1, Now.second));
		}
	}
	//hidari
	if(Now.second - 1 >= 0 && S[Now.first][Now.second - 1] != 'X'){
		if(cost[Now.first][Now.second] + 1 < cost[Now.first][Now.second - 1]){
			 cost[Now.first][Now.second - 1] = cost[Now.first][Now.second] + 1;
			 que.push(make_pair(Now.first, Now.second - 1));
		}
	}
	//r
	if(Now.second +1 < w && S[Now.first][Now.second + 1] != 'X'){
		if(cost[Now.first][Now.second] + 1 < cost[Now.first][Now.second + 1]){
			 cost[Now.first][Now.second + 1] = cost[Now.first][Now.second] + 1;
			 que.push(make_pair(Now.first , Now.second + 1));
		}
	}
	
}

int main(){
	//チーズ
	
	cin >> h >> w >> n;

	for(int i=0; i<h; i++){
		cin >> S[i];
	}

	for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
			if(S[i][j] == 'S'){
				factory[0] = make_pair(i, j);
			}
			else if(S[i][j] != 'X' && S[i][j] != '.'){
				factory[S[i][j]-'0'] = make_pair(i,j);
			}
		}
	}


	int ans = 0;
	for(int i=0; i<n; i++){
		
		for(int j=0; j<h; j++){
			for(int k=0; k<w; k++){
				cost[j][k] = 999999;
			}
		}

		cost[factory[i].first][factory[i].second] = 0;
		que.push(factory[i]);
		while(!que.empty()){
			Solve(que.front());
			que.pop();
		}
		ans += cost[factory[i+1].first][factory[i+1].second];
	}

	cout << ans << endl;


	return 0;	
}
*/

	//宝探し
	/*
	int n,m;
	cin >> n >> m;
	int A[5100][5100];
	//A[0][0] = 0;
	/*
	for(int i=0; i<5000; i++){
		for(int j=0; j<5000; j++){
			//A[i+1][j+1] = A[i+1][j] + A[i][j+1] -A[;
			
		}
	}
	*/
	/*
	int Px[5000],Py[5000];
	for(int i=0; i<n; i++){
		int x,y;
		cin >> x >> y;
		
		//A[x][y] = 1;
	}
	
	int B[5100][5100];
	B[0][0] = 0;
	for(int i=0; i<100; i++){
		for(int j=0; j<100; j++){
			B[i+1][j+1] = B[i+1][j] + B[i][j+1] - B[i][j] + A[i+1][j+1];
		}
	}

	for(int i=0; i<m; i++){
		int x,y,X,Y;
		cin >> x >> y >> X >> Y;
		cout << B[x][y] - B[X-1][Y-1] << endl;
	}
	*/


	//超観光都市
	/*
		int w,h,n;
		cin >> w >> h >> n;
		int ans = 0;
		int X,Y;
		int x,y;
		cin >> x >> y;
		X = x;
		Y = y;

		for(int i=0; i<n-1; i++){
			cin >> x >> y;
			bool hugou = ((x-X>0&&y-Y>0)||(x-X<0&&y-Y<0));
			if(hugou == 1){
				ans += max(abs(x-X), abs(y-Y));
			}
			else{
				ans += abs(x-X)+abs(y-Y);
			}
			X = x;
			Y = y;
		}
		cout << ans << endl;
*/
	//すごろく
	/*
	while(true){
		int n,m;
		cin >> n >> m;
	if(n==0 && m==0) break;

		int X[1000],Y;
		for(int i=0 ; i<n; i++){
			cin >> X[i];
		}

		int i,a=0;
		for(i=0; i<m; i++){
			cin >> Y;
			a += Y;
			a += X[a];
			if(a+1>=n) break;
		}
		cout << i + 1<< endl;
	}
	*/

	//看板(未完成）
	/*
	int n,Ans;
	string name;
	cin >> n >> name;
	for(int i=0; i<n; i++){
		string s;
		cin >> s;
		int x[100];
        int l=0;
		for(int j=0; j<name.size(); j++){
			for(int k=0; k<s.size(); k++){		
				if(name[j]==s[k]){
					x[l]=k;
					l++;
				}
			}
		}
		int p=x[1]-x[0];
		for(int j=1; j<l+1; j++){
			if(p!=x[j]-x[j-1])
				break;
			

		}
	}
	*/
	//サッカー
	/*
	int n;
	cin >> n;
	int P[100];
	for(int i = 0; i<n; i++){
		P[i]=0;
	}
	
	for(int i=0; i<n*(n-1)/2; i++){
		int a,b,c,d;
		cin >> a >> b >> c >> d;
		if(c>d)
			P[a-1] += 3; 
		if(c==d){
			P[a-1]++;
			P[b-1]++;
		}
		if(c<d)
			P[b-1] += 3;
	}

	int Q[100];
	for(int i =0; i<n; i++){
		Q[i] = P[i];
	}
	sort(Q, Q+n);
	reverse(Q,Q+n);
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(P[i]==Q[j]){
				cout << j+1 << endl;
				break;
			}
		}
	}
	*/

	//気象予報士
	/*
		int h,w;
		int x=-1;
		cin >> h >> w;
		
		for(int i=0; i<h; i++){
			for(int j =0; j<w; j++){
				char a;
				cin >> a;
				if(a=='c'){
					cout << 0;
					x = j;
				}
				else if(x != -1){
					cout << j-x;
				}
				else
					cout << -1;
				if(j==w-1)
					break;
				cout << " ";
			}
			cout << endl;
			x = -1;
		}
		*/

	/*
	//数あて
	int n;
	cin >> n;
	int p[200][3];

	for(int i=0;i<n;i++)
	{
		cin >> p[i][0] >> p[i][1] >> p[i][2];
	}

	int _p;
	for(int k=0;k<3;k++)
	{
		for(int i=0;i<n;i++)
		{
			_p = p[i][k];
			for(int j=i+1;j<n;j++)
			{
				if(_p == p[j][k])
				{
					p[i][k] = 0;
					p[j][k] = 0;
				}
			}
		}
	}

	for(int i=0;i<n;i++)
	{
		cout << p[i][0] + p[i][1] + p[i][2] << endl;
	}
	*/

	/*
	//得点
	int ai,am,as,ae,bi,bm,bs,be;
	cin >> ai >> am >> as >> ae >> bi >> bm >> bs >> be;
	int answer=ai+am+as+ae;
	if(answer < bi+bm+bs+be)
	{
	/	answer=bi+bm+bs+be;
	}
	cout << answer << endl;
	*/
	
	//おつり
/*	int onum;
	while(true){
		int N;
		cin >> N;
		if(N == 0) break;
		onum=0;
		int oturi = 1000-N;
		if(oturi >= 500)
		{
			onum++;
			oturi -= 500;
		}
		while(oturi>=100)
		{
			onum++;
			oturi -= 100;
		}
		if(oturi >= 50)
		{
			onum++;
			oturi -= 50;
		}
		while(oturi>=10)
		{
			onum++;
			oturi -= 10;
		}
		if(oturi >= 5)
		{
			onum++;
			oturi -= 5;
		}
		while(oturi>=1)
		{
			onum++;
			oturi -= 1;
		}
		 cout << onum << endl;
	}
   */

	//レシート
	/*
	while(true){
		int N;
		cin >> N;
		if(N==0) break;
		int a[9];
		for(int i=0;i<9;i++){
			cin >> a[0];
		}

	}
	
	/*
	int N;
	int i = 0;
	while(i<N){
		i++;
	}
	for(int i=0; i<N; i++)
	*/
	/*
	int N;
	int x;
	set<int> a;
	cin >> N;
	for(int i=0; i<N; i++){
		cin >> x;
		a.insert(x);
	}
	cout << a.size() << endl;
	*/
	
	//投票
	/*
	int N,M;
	cin >> N >> M;
	int a;
	int A[1000];
	int B[1000];
	int X[1000][2];
	
	for(int i=0; i<N; i++){
		cin >> A[i];
		X[i][0] = i;
		X[i][1] = 0;
	}
	for(int j=0; j<M;j++){
		cin >> B[j];
	}
	for(int j=0; j<M; j++){
		for(int i=0; i<N; i++){
			if(A[i] <= B[j]){
				X[i][1]++;
				break;
			}
		}
	}
	for(int i=1; i<N; i++){
		if(X[i-1][1]<X[i][1])
			X[i-1][0] = X[i][0];
	}
	cout << X[0][0]+1 << endl;
	*/
	/*
	int N,M;
	cin >> N >> M;
	int A[1000];
	int vote[1000];
	for(int i=0; i<N; i++){
		cin >> A[i];
		vote[i] =0;
	}
	int B;
	for(int i=0; i<M; i++){
		cin >> B;
		for(int j=0; j<N; j++){
			if(A[j]<=B){
				vote[j]++;
				break;
			}
		}
	}
	int temps = 0;
	int ans=0;
	for(int i=0; i<N; i++){
		if(vote[i] >= temps){
			temps = vote[i];
			ans = i;
		}
	}
	cout << ans+1 << endl;
	*/

//	return 0;
//}
/*
int max(int i,int j){
	if(i < j) i=j;
	return i;
}
*/

컴파일 시 표준 에러 (stderr) 메시지

gap.cpp:1341:2: warning: "/*" within comment [-Wcomment]
  /*
   
gap.cpp:1513:1: warning: "/*" within comment [-Wcomment]
 /*
  
gap.cpp:1516:2: warning: "/*" within comment [-Wcomment]
  /*
   
gap.cpp:2082:2: warning: "/*" within comment [-Wcomment]
  /*
   
gap.cpp:2357:2: warning: "/*" within comment [-Wcomment]
  /*
   
In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from gap.cpp:11:
gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:47:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   assert(a.size() == N):
          ~~~~~~~~~^~~~
gap.cpp:47:24: error: expected ';' before ':' token
   assert(a.size() == N):
                        ^