/*#include <stdio.h>
char arr[401][401]={};
int w, h;
int dir[8][2]={-1,0,+1,0,0,+1,0,-1,-1,-1,-1,+1,+1,-1,+1,+1};
void dfs(int i, int j)
{
if(arr[i][j]=='.' || i<=0 || j<=0 || i>h || j>w) return ;//범위넘거나 0이라면
arr[i][j]='.'; // 방문했다!
for(int k=0;k<8;k++)
dfs(i+dir[k][0],j+dir[k][1]);
// dfs(i-1,j); //위
// dfs(i+1,j); //아래
// dfs(i,j-1); //왼쪽
// dfs(i,j+1); //오른쪽
// dfs(i-1,j-1); //왼쪽 위
// dfs(i-1,j+1); //오른쪽 위
// dfs(i+1,j-1);//왼쪽 아래
// dfs(i+1,j+1);//오른쪽 아래
}
int main()
{
int cnt=0;
scanf("%d %d",&w,&h);
for(int i=1;i<=h;i++)
{
for(int j=1;j<=w;j++)
{
scanf(" %c",&arr[i][j]);
}
}
for(int i=1;i<=h;i++)
{
for(int j=1;j<=w;j++)
{
if(arr[i][j]=='L')
{
cnt++;
dfs(i,j);
}
}
}
printf("%d",cnt);
return 0;
}
*/
/*
#include <stdio.h>
int arr[8][8]={};
int a=1,b=2,c=3,d=4,e=5,v=0;
int dir[4][2]={-1,0,+1,0,0,+1,0,-1,};
void dfs(int i, int j,int n)
{
if(arr[i][j]==0 || arr[i][j]!=n || i<=0 || j<=0 || i>7 || j>7) return ;
arr[i][j]=0; // 방문했다
v++;
for(int k=0;k<4;k++)
dfs(i+dir[k][0],j+dir[k][1],n);
}
int main()
{
int cnt=0;
for(int i=1;i<=7;i++)
{
for(int j=1;j<=7;j++)
{
scanf("%d",&arr[i][j]);
}
}
for(int i=1;i<=7;i++)
{
for(int j=1;j<=7;j++)
{
if(arr[i][j]==a)
{
dfs(i,j,a);
if(v>=3)
cnt++;
v=0;
}
else if(arr[i][j]==b)
{
dfs(i,j,b);
if(v>=3)
cnt++;
v=0;
}
else if(arr[i][j]==c)
{
dfs(i,j,c);
if(v>=3)
cnt++;
v=0;
}
else if(arr[i][j]==d)
{
dfs(i,j,d);
if(v>=3)
cnt++;
v=0;
}
else if(arr[i][j]==e)
{
dfs(i,j,e);
if(v>=3)
cnt++;
v=0;
}
}
}
printf("%d",cnt);
return 0;
}
*/
/*
#include <stdio.h>
int arr[27][27]={},n;
int danji[500]={};
int a=0;
void dfs(int i, int j)
{
if(arr[i][j]==0) return ;//범위넘거나 0이라면
arr[i][j]=0; // 방문했다
a++;
dfs(i-1,j);
dfs(i+1,j);
dfs(i,j-1);
dfs(i,j+1);
}
int main()
{
int cnt=0,temp;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%1d",&arr[i][j]);
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(arr[i][j]==1)
{
cnt++;a=0;
dfs(i,j);
danji[cnt]=a;
}
}
}
printf("%d\n",cnt);
// 정렬
for(int i=1; i<cnt; i++)
{
for(int j=1;j<=cnt-i;j++)
{
if (danji[j] > danji[j+1])
{
temp = danji[j];
danji[j] = danji[j+1];
danji[j+1] = temp;
}
}
}
for(int i=1;i<=cnt;i++)
printf("%d\n",danji[i]);
return 0;
}
*/
/*
#include <stdio.h>
int arr[101][101]={},m,n,k;
int binkan[500]={};
int cnt=0;
void dfs(int i, int j)
{
if(i<0|| j<0||j>=n||i>=m||arr[i][j]==1) return ;//범위넘거나 0이라면
arr[i][j]=1; // 방문했다
binkan[cnt]++;
dfs(i-1,j);
dfs(i+1,j);
dfs(i,j-1);
dfs(i,j+1);
}
int main()
{
int temp,a,b,c,d;
scanf("%d %d %d",&m,&n,&k);
for(int i=0;i<k;i++)
{
scanf("%d %d %d %d",&a ,&b ,&c ,&d );
for(int e=b;e<d;e++)
{
for(int f=a;f<c;f++)
{
arr[e][f]=1;
}
}
}
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(arr[i][j]==0)
{
cnt++;
dfs(i,j);
}
}
}
printf("%d\n",cnt);
// 정렬
for(int i=1; i<cnt; i++)
{
for(int j=1;j<=cnt-i;j++)
{
if (binkan[j] > binkan[j+1])
{
temp = binkan[j];
binkan[j] = binkan[j+1];
binkan[j+1] = temp;
}
}
}
for(int i=1;i<=cnt;i++)
printf("%d ",binkan[i]);
return 0;
}
*/