/*#include <bits/stdc++.h>
using namespace std;
int cnt, n;
void dab(int x, int y)
{
if(x==n)
{
cnt++;
return ;
}
if(x>n)
return ;
if(y==0)
{
dab(x+3, 2);
dab(x+1, 0);
dab(x+2, 0);
}
else
{
dab(x+1, y-1);
dab(x+2, y-1);
return ;
}
}
int main()
{
scanf("%d", &n);
int dp[16][4]= {};
dab(0, 0);
printf("%d", cnt);
}*/
/*
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
scanf("%d", &n);
int dp[21][2]={};
dp[1][0]=1, dp[1][1]=1;
for(int i=2;i<=n;i++)
{
dp[i][1]=dp[i-1][0]+dp[i-1][1];
dp[i][0]=dp[i-1][1];
}
printf("%d", dp[n][1]+dp[n][0]);
}*/
/*
#include <bits/stdc++.h>
using namespace std;
int dab(int x, int y, int z)
{
if(x<0)
return 0;
if(y==0)
return 1;
if(z==0)
{
return dab(x-2, y-1, 1)+dab(x-1, y, 1);
}
else
{
return dab(x-1, y-1, 0)+dab(x-1, y, 1);
}
}
int main()
{
int n, k;
scanf("%d %d", &n, &k);
printf("%d", dab(n, k, 0));
}*/
/*
#include <bits/stdc++.h>
using namespace std;
int main()
{
int arr[11];
int ans[7];
int sum=0, top=-1;
for(int i=1; i<=9; i++)
{
cin >> arr[i];
sum+=arr[i];
}
for(int i=1; i<=9; i++)
{
for(int j=1; j<=9; j++)
{
if(i==j)
continue;
if(sum-arr[i]-arr[j]==100)
{
for(int k=1; k<=9; k++)
{
if(k!=i&&k!=j)
{
top++;
ans[top]=arr[k];
}
}
sort(ans, ans+7);
for(int p=0; p<7; p++)
printf("%d\n", ans[p]);
return 0;
}
}
}
}*/
/*
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
scanf("%d", &n);
int arr[16][3];
int dp[16][3];
for(int i=1;i<=n;i++)
scanf("%d %d %d", &arr[i][0], &arr[i][1], &arr[i][2]);
dp[1][0]=arr[1][0];
dp[1][1]=arr[1][1];
dp[1][2]=arr[1][2];
for(int i=2;i<=n;i++)
{
dp[i][0]=min(dp[i-1][2], dp[i-1][1])+arr[i][0];
dp[i][1]=min(dp[i-1][0], dp[i-1][2])+arr[i][1];
dp[i][2]=min(dp[i-1][0], dp[i-1][1])+arr[i][2];
}
printf("%d", min(min(dp[n][0], dp[n][1]), dp[n][2]));
}*/
/*
#include <bits/stdc++.h>
using namespace std;
int dab(int x)
{
if(x==1)
return 1;
if(x==2)
return 2;
return dab(x-1)+dab(x-2);
}
int main()
{
int n;
scanf("%d", &n);
printf("%d", dab(n));
}*/
/*
#include <bits/stdc++.h>
using namespace std;
int a, b, c, d, cnt=2100000000;
map<pair<int, int>, int> visited;
void dab(int x, int y, int z)
{
if(visited.find({x, y})!=visited.end()&&visited[ {x, y}]<z)
return ;
if(visited.find({x, y})!=visited.end()&&visited[ {x, y}]>z)
{
visited[ {x, y}]=z;
}
else
{
visited.insert({{x, y}, z});
}
if(x==c&&y==d)
{
cnt=min(cnt, z);
//printf("%d", z);
}
if(x<a)
{
dab(a, y, z+1);
}
if(x>0)
{
dab(0, y, z+1);
}
if(b-y>=x)
{
dab(0, y+x, z+1);
}
{
dab(x-(b-y), b, z+1);
}
if(y<b)
{
dab(x, b, z+1);
}
if(y>0)
{
dab(x, 0, z+1);
}
if(a-x>=y)
{
dab(x+y, 0, z+1);
}
else
{
dab(a, y-(a-x), z+1);
}
}
int main()
{
scanf("%d %d %d %d", &a, &b, &c, &d);
dab(0, 0, 0);
if(visited.find({c, d})!=visited.end())
{
printf("%d", cnt);
}
else
{
printf("-1");
}
}*/
/*
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a, b, c, d;
scanf("%d %d %d %d", &a, &b, &c, &d);
int t=0, k=0;
int x=0, y=0;
if(a==c&&b==d)
{
printf("2");
return 0;
}
while(1)
{
if(y==b)
{
y=0;
}
else if(x==0)
{
x=a;
}
else if(x+y<b)
{
y+=x;
x=0;
}
else
{
x-=(b-y);
y=b;
}
t++;
if(x==c&&y==d)
k=t;
if(x==0&&y==0)
break;
}
if(k==0)
{
printf("-1");
return 0;
}
else
{
printf("%d", min(k, t-k));
}
}*/
/*
#include <bits/stdc++.h>
using namespace std;
int n;
bool zero(int x)
{
return !x;
}
int main()
{
scanf("%d", &n);
if(zero(n)) printf("zero");
else printf("non zero");
return 0;
}*/
/*
#include <bits/stdc++.h>
using namespace std;
int n;
bool zero(int x)
{
return !x;
}
bool plus(int x)
{
return x>0;
}
int main()
{
scanf("%d", &n);
if(zero(n)) printf("zero");
else printf("%s", Plus(n)?"plus":"minus");
return 0;
}*/
/*
#include <bits/stdc++.h>
using namespace std;
long long int f(double x)
{
long long int t=(long long int)x;
if(t<x)
return x+1;
else
return x;
}
int main()
{
}*/
/*
#include <bits/stdc++.h>
using namespace std;
int main()
{
int arr[5];
for(int i=0;i<5;i++)
scanf("%d", &arr[i]);
for(int i=4;i>=0;i--)
printf("%d ", arr[i]);
}*/
/*
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
printf("%d %d %d", c, b, a);
}*/
/*
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s;
getline(cin, s);
for(int i=0;i<s.size();i++)
{
if(s[i]==',')
{
printf(" ");
continue;
}
if(s[i]==' ')
continue;
if(s[i]==';')
{
printf("\n");
continue;
}
printf("%c", s[i]);
}
}*/