/*#include<stdio.h>
int n,m,a[20]={};
int x(int p,int q){
if(q==m){
if(p==0)return 1;
return 0;
}
return x(p-a[q],q+1)+x(p+a[q],q+1);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
scanf("%d",&a[i]);
}
printf("%d",x(n,0));
return 0;
}*/
//덧셈, 뺄셈으로 n만들기
/*#include<stdio.h>
int n,k,a[33]={1};
int sit(int p, int q){
int s=0;
if(p+q>n+1){
}else if(q==0){
s=1;
}else{
s=sit(p+1,q);
if(p==1||(a[p-2]+a[p-1]<2&&a[p-1]+a[p+1]<2)){
a[p]=1;
s+=sit(p+1,q-1);
a[p]=0;
}
}
return s;
}
int main(){
scanf("%d%d",&n,&k);
a[n+1]=1;
printf("%d",sit(1,k));
}*/
//극장 좌석 배치 3
/*#include<stdio.h>
int main(){
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
if((a-c)*(a-d)*(b-c)*(b-d)<0){
printf("cross");
}else{
printf("not cross");
}
return 0;
}*/
//케잌 자르기
/*#include<stdio.h>
int n;
int stair(int k,int t){
if(k<0)return 0;
if(k==0)return 1;
int s=stair(k-1,t-1);
s+=stair(k-2,t-1);
if(t<0)s+=stair(k-3,1);
return s;
}
int main(){
scanf("%d",&n);
printf("%d",stair(n,-1));
return 0;
}*/
//숏다리의 계단 오르기(small)
/*#include<stdio.h>
int main(){
int n;
scanf("%d",&n);
int s=0;
for(int i=1;i<(n+1)/2;i++){
for(int j=i;j<(n+1)/2;j++){
if(i+2*j<=n&&2*i+2*j>n)s++;
}
}
printf("%d",s);
}*/
//삼각형 화단 만들기
/*#include<stdio.h>
int main(){
int n,k,x;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&x);
if(x>=k){
printf("%d",i);
return 0;
}
}
printf("%d",n+1);
return 0;
}*/
//Lower Bound
/*#include<stdio.h>
int n,s,a[21]={};
int r(int x,int y){
if(x==n)return y?0:1;
int z=r(x+1,y)+r(x+1,y-a[x]);
return z;
}
int main(){
scanf("%d%d",&n,&s);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
if(s==0){
printf("%d",r(0,s)-1);
}else{
printf("%d",r(0,s));
}
return 0;
}*/
//부분수열의 합
/*#include<stdio.h>
int a,b,c,d,m=11;
struct w{
int aa;
int bb;
};
struct w wa[11]={};
void water(int A,int B,int k){
if(k>=m)return;
for(int i=0;i<k;i++){
if(wa[i].aa==A&&wa[i].bb==B)return;
}
if(A==c&&B==d&&k<m){
m=k;
return;
}
wa[k].aa=A;
wa[k].bb=B;
water(a,B,k+1);
water(A,b,k+1);
water(0,B,k+1);
water(A,0,k+1);
int move=A<(b-B)?A:(b-B);
water(A-move,B+move,k+1);
move=B<a-A?B:a-A;
water(A+move,B-move,k+1);
wa[k].aa=0;
wa[k].bb=0;
}
int main(){
scanf("%d%d%d%d",&a,&b,&c,&d);
water(0,0,0);
if(m==11){
printf("-1");
return 0;
}
printf("%d",m);
return 0;
}*/
//물통(tiny)
/*#include<stdio.h>
int a[9][9]={},s=0;
int c(int x,int y,int f){
if(a[x][y]-f)return 0;
a[x][y]=0;
return 1+c(x-1,y,f)+c(x+1,y,f)+c(x,y+1,f)+c(x,y-1,f);
}
int main(){
for(int i=1;i<8;i++){
for(int j=1;j<8;j++){
scanf("%d",&a[i][j]);
}
}
for(int i=1;i<8;i++){
for(int j=1;j<8;j++){
if(a[i][j]&&c(i,j,a[i][j])>2)s++;
}
}
printf("%d",s);
return 0;
}*/
//캔디팡
/*#include<stdio.h>
int a[102][102]={},b[102][102]={},s1=0,s2=0,m,n;
void c(int x,int y){
if(a[x][y])return;
a[x][y]=1;
c(x-1,y);
c(x+1,y);
c(x,y+1);
c(x,y-1);
}
void d(int x,int y){
if(b[x][y]==0)return;
b[x][y]=0;
d(x-1,y);
d(x+1,y);
d(x,y+1);
d(x,y-1);
}
int main(){
scanf("%d%d",&m,&n);
for(int i=0;i<m+2;i++){
for(int j=0;j<n+2;j++){
a[i][j]=1;
}
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
scanf("%d",&a[i][j]);
b[i][j]=a[i][j];
}
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(a[i][j]==0){
c(i,j);
s1++;
}
if(b[i][j]){
s2++;
d(i,j);
}
}
}
printf("%d %d",s1,s2);
return 0;
}*/
//전광판 전구 조작
/*#include<stdio.h>
int a[21][21]={};
int omok(int x,int y,int xup,int yup,int color,int length){
if(length==6)return 0;
if(a[x][y]!=color){
if(length==5)return 1;
return 0;
}
return omok(x+xup,y+yup,xup,yup,color,length+1);
}
int main(){
for(int i=1;i<20;i++){
for(int j=1;j<20;j++){
scanf("%d",&a[i][j]);
}
}
for(int i=1;i<20;i++){
for(int j=1;j<20;j++){
if(a[i][j]){
for(int xup=-1;xup<2;xup++){
for(int yup=-0;yup<2;yup++){
if(a[i-xup][j-yup]!=a[i][j]&&omok(i,j,xup,yup,a[i][j],0)){
printf("%d\n%d %d",a[i][j],i,j);
return 0;
}
}
}
}
}
}
printf("0");
return 0;
}*/
//오목
/*#include<stdio.h>
int a[1002][1002]={},n,m;
int r(int bx,int by,int x,int y){
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
a[i][j]++;
}
}
printf("%d",)
return 0;
}*/
//놀이공원(푸는중)