/*#include <bits/stdc++.h>
using namespace std;
int n, top, cnt=0;
char ans[8];
void haha(int x, int y)
{
if(x==n)
{
cnt++;
if(cnt%2==0)
return ;
for(int i=1;i<=top;i++)
printf("%c", ans[i]);
printf("\n");
return ;
}
if(y==0)
{
top++;
ans[top]='O';
haha(x+1, 0);
haha(x+1, 1);
top--;
}
else
{
top++;
ans[top]='X';
haha(x+1, 0);
haha(x+1, 1);
top--;
}
}
int main()
{
scanf("%d", &n);
haha(0, 0);
haha(0, 1);
}*/
/*
#include <bits/stdc++.h>
using namespace std;
int gavi[10][10]={}, sevi[10][10]={}, arr[10][10], ha=0, boxvi[10][10];
int boxn(int x, int y)
{
int box=1;
if(x==1||x==2||x==3)
{
box=1;
}
else if(x==4||x==5||x==6)
{
box=4;
}
else
{
box=7;
}
if(y==4||y==5||y==6)
{
box++;
}
else if(y==7||y==8||y==9)
{
box+=2;
}
return box;
}
void ans(int x, int y)
{
if(x==10&&ha==0)
{
for(int i=1;i<=9;i++)
{
for(int j=1;j<=9;j++)
printf("%d ", arr[i][j]);
printf("\n");
}
ha=1;
return ;
}
if(y==10)
{
ans(x+1, 1);
return ;
}
if(arr[x][y]!=0)
{
ans(x, y+1);
return ;
}
int possible[10]={}, top=0;
for(int i=1;i<=9;i++)
{
if(gavi[x][i]==0&&sevi[y][i]==0&&boxvi[boxn(x, y)][i]==0)
{
top++;
possible[top]=i;
}
}
for(int i=1;i<=top;i++)
{
int con=possible[i];
gavi[x][con]=1;
sevi[y][con]=1;
boxvi[boxn(x, y)][con]=1;
arr[x][y]=con;
ans(x, y+1);
gavi[x][con]=0;
sevi[y][con]=0;
boxvi[boxn(x, y)][con]=0;
arr[x][y]=0;
}
}
int main()
{
for(int i=1;i<=9;i++)
{
for(int j=1;j<=9;j++)
scanf("%d", &arr[i][j]);
}
int temp;
for(int i=1;i<=9;i++)
{
for(int j=1;j<=9;j++)
{
if(arr[i][j]!=0)
{
boxvi[boxn(i, j)][arr[i][j]]=1;
gavi[i][arr[i][j]]=1;
sevi[j][arr[i][j]]=1;
}
}
}
ans(1, 1);
if(ha==0)
{
printf("Not Possible");
}
}*/
/*
#include <bits/stdc++.h>
using namespace std;
int n, ans[81], top, hahaha;
void haha(int x, int y)
{
// printf("haha\n");
if(top==n&&hahaha==0)
{
for(int i=1;i<=top;i++)
printf("%d", ans[i]);
hahaha=1;
return ;
}
if(x==n+1)
return ;
top++;
ans[top]=y;
int a=2, b, c;
while(a<=x)
{
c=1;
b=a/2;
for(int i=x-a+1;i<=x-b;i++)
{
if(ans[i]!=ans[i+b])
{
c=0;
break;
}
}
if(c==1){
top--;
return ;
}
a+=2;
}
for(int i=1;i<=3;i++)
{
if(i!=y&&hahaha==0)
{
haha(x+1, i);
}
}
top--;
}
int main()
{
scanf("%d", &n);
haha(1, 1);
}*/
/*
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
scanf("%d", &n);
if(n==1)
{
printf("2");
return 0;
}
int ans=4, cur=2;
for(int i=3;i<=n;i++)
{
ans+=cur+1;
cur++;
ans%=137;
}
printf("%d", ans);
}*/
/*
#include <bits/stdc++.h>
using namespace std;
int main()
{
int k, temp, mo, top=0;
scanf("%d", &k);
string s;
cin >> s;
char ans[21]={};
for(int i=0;i<s.size();i++)
{
mo=3*(i+1)+k;
temp=26+s[i]-'A'+1-mo;
if(temp!=26)
temp%=26;
top++;
ans[top]=temp+'A'-1;
}
for(int i=1;i<=top;i++)
printf("%c", ans[i]);
}*/
/*
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, cur, old;
float sum=0;
scanf("%d", &n);
string s;
for(int i=1;i<=n;i++)
{
cin >> s;
for(int i=1;i<s.size();i++)
{
if(s[i]=='M'||s[i]=='F')
{
cur=i+2;
old=s[cur]-'0';
cur++;
while(s[cur]!=',')
{
old*=10;
old+=s[cur]-'0';
cur++;
}
break;
}
}
sum+=old;
}
printf("%.2f", sum/(float)n);
}*/
/*
#include <bits/stdc++.h>
using namespace std;
int main()
{
int prime[4000001]={}, a, b;
scanf("%d %d", &a, &b);
for(int i=3;i<=2000;i++)
{
for(int j=i*2;j<=4000000;j+=i)
{
prime[j]=1;
}
}
for(int i=a;i<=b;i++)
{
if(i%2==0)continue;
if(prime[i]==0&&prime[i+2]==0&&i+2<=b)
{
printf("%d %d\n", i, i+2);
}
}
}*/
/*
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, i;
scanf("%d", &n);
long long int sum=0;
for(i=1;i*i<n;i++)
{
if(n%i==0)
sum+=i+n/i;
}
if(i*i==n)sum+=i;
printf("%lld", sum);
}*/
/*
#include <bits/stdc++.h>
using namespace std;
string s;
int hab(int x, int y)
{
int sum=0;
for(int i=x;i<=y;i++)
{
sum*=10;
sum+=s[i]-'0';
}
return sum;
}
int main()
{
long long int dp[1001]={}, k;
scanf("%d", &k);
cin >> s;
dp[0]=s[0]-'0';
for(int i=1;i<s.size();i++)
{
if(i+1<=k)
dp[i]=hab(0, i);
for(int j=1;i-j>=0;j++)
{
if(j>k)break;
dp[i]=max(dp[i], dp[i-j]+hab(i-j+1, i));
}
}
printf("%lld", dp[s.size()-1]);
}*/