/*#include <bits/stdc++.h>
using namespace std;
int main()
{
string s;
cin >> s;
int cnt=0;
if(s.size()>=1)
{
if(s[0]=='3'||s[0]=='6'||s[0]=='9')
cnt++;
}
if(s.size()>=2)
{
if(s[1]=='3'||s[1]=='6'||s[1]=='9')
cnt++;
}
if(s.size()>=3)
{
if(s[2]=='3'||s[2]=='6'||s[2]=='9')
cnt++;
}
if(cnt==1)
{
printf("K");
return 0;
}
if(cnt==2)
{
printf("KK");
return 0;
}
if(cnt==3)
{
printf("KKK");
return 0;
}
cout<<s;
}
*/
/*
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, s;
scanf("%d %d", &n, &s);
int arr[100001]={};
for(int i=1;i<=n;i++)
scanf("%d", &arr[i]);
int mid, start=1, End=n;
while(start<=End)
{
mid=(start+End)/2;
if(arr[mid]<s)
{
start=mid+1;
}
else if(arr[mid]>s)
{
End=mid-1;
}
else
{
printf("%d", mid);
return 0;
}
}
printf("-1");
}*/
/*
#include <bits/stdc++.h>
using namespace std;
int a, n, arr[22]={}, ans=0;
void haha(int x, int y)
{
if(y==n+1&&x<a)
{
ans=max(ans, x);
return ;
}
if(x>a)
{
return ;
}
haha(x+arr[y], y+1);
haha(x, y+1);
}
int main()
{
scanf("%d", &a);
scanf("%d", &n);
for(int i=1;i<=n;i++)
scanf("%d", &arr[i]);
haha(0, 1);
printf("%d", ans);
}
*/
/*
#include <bits/stdc++.h>
using namespace std;
int arr[7][3], puha[7][3], ans;
void haha(int x, int y, int z)
{
for(int i=1;i<=6;i++)
{
for(int j=0;j<=2;j++)
{
if(arr[i][j]<puha[i][j]||arr[i][j]>=6)
return ;
}
}
if(z==16)
{
ans=1;
}
if(y>6)
{
x++;
y=x+1;
}
puha[x][0]++;
puha[y][2]++;
haha(x, y+1, z+1);
puha[x][0]--;
puha[y][2]--;
puha[x][1]++;
puha[y][1]++;
haha(x, y+1, z+1);
puha[x][1]--;
puha[y][1]--;
puha[x][2]++;
puha[y][0]++;
haha(x, y+1, z+1);
puha[x][2]--;
puha[y][0]--;
}
int main()
{
for(int ppp=0;ppp<=3;ppp++)
{
memset(puha, 0, sizeof(puha));
ans=0;
for(int i=1;i<=6;i++){
for(int j=0;j<=2;j++){
scanf("%d", &arr[i][j]);}
}
haha(1, 2, 1);
printf("%d ", ans);
}
}*/
/*
#include <bits/stdc++.h>
using namespace std;
int n;
int cnt, visited[14], arr[14], visit[14][14];
void chess(int x)
{
if(x==n+1)
{
if(cnt<3){
for(int i=1;i<=n;i++)
printf("%d ", arr[i]);
printf("\n");}
cnt++;
return ;
}
for(int i=1;i<=n;i++)
{
int boo=1;
for(int j=x;j>=1;j--)
{
if(visit[j][i]||(i-(x-j)>0&&visit[j][i-(x-j)])||(i+(x-j)<=n&&visit[j][i+(x-j)]))
{
boo=0;
break;
}
}
if(boo)
{
visit[x][i]=1;
arr[x]=i;
chess(x+1);
visit[x][i]=0;
}
}
}
int main()
{
scanf("%d", &n);
chess(1);
printf("%d", cnt);
}*/