#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;
}
*/
Compilation message
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):
^
