/*#include <stdio.h>
#include<math.h>
double cityr[10000]={};
int cityp[10000]={};
void swap(int l,int r){
double t=cityr[l];
cityr[l]=cityr[r];
cityr[r]=t;
int tt=cityp[l];
cityp[l]=cityp[r];
cityp[r]=tt;
}
int piv(int begin,int end){
int p=begin;
int l=begin+1;
int r=end;
while(l<r){
while(cityr[l]<=cityr[p]&&l<=r)l++;
while(cityr[r]>=cityr[p]&&l<=r)r--;
double t=cityr[l];
cityr[l]=cityr[r];
cityr[r]=t;
int tt=cityp[l];
cityp[l]=cityp[r];
cityp[r]=tt;
}
if(cityr[p]>cityr[l]){
t=cityr[l];
cityr[l]=cityr[p];
cityr[p]=t;
tt=cityp[p];
cityp[p]=cityp[l];
cityp[l]=tt;
}
return l;
}
void quick(int begin,int end){
if(begin>=end)return;
int p=piv(begin,end);
quick(begin,p-1);
quick(p,end);
return;
}
int main()
{
int n,p,x,y;
scanf("%d%d",&n,&p);
for(int i=0;i<n;i++){
scanf("%d%d%d",&x,&y,&cityp[i]);
cityr[i]=sqrt(x*x+y*y);
}
quick(0,n-1);
int i=0;
for(i;i<n;i++){
p+=cityp[i];
if(p>=1000000){
printf("%.3lf",cityr[i]);
return 0;
}
}
printf("-1");
return 0;
}*/
// 광역시
/*#include<stdio.h>
char a[101][101]={};
void lake(int x,int y){
if(a[x][y]!='L')return;
a[x][y]='.';
lake(x-1,y-1);
lake(x,y-1);
lake(x+1,y-1);
lake(x+1,y);
lake(x+1,y+1);
lake(x,y+1);
lake(x-1,y+1);
lake(x-1,y);
return;
}
int main(){
int w,h;
char enter;
scanf("%d %d",&w,&h);
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
scanf(" %c",&a[i][j]);
}
}
int n=0;
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
if(a[i][j]=='L'){
lake(i,j);
n++;
}
}
}
printf("%d",n);
return 0;
}*/
//호수의 수 구하기
/*#include<stdio.h>
int a[100][100]={};
int res[5000]={};
int lake(int x,int y){
if(a[x][y]==0)return 0;
a[x][y]=0;
return (lake(x-1,y)+lake(x+1,y)+lake(x,y-1)+lake(x,y+1)+1);
}
int main(){
int m,n,k,x1,x2,y1,y2,t;
scanf("%d%d%d",&m,&n,&k);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
a[i][j]=1;
}
}
for(int i=0;i<k;i++){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
for(int j=x1;j<x2;j++){
for(int ij=y1;ij<y2;ij++){
a[j][ij]=0;
}
}
}
int s=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(a[i][j]){
res[s]=lake(i,j);
s++;
}
}
}
printf("%d\n",s);
for(int i=1;i<s;i++){
for(int j=0;j<s-i;j++){
if(res[j+1]<res[j]){
t=res[j];
res[j]=res[j+1];
res[j+1]=t;
}
}
}
for(int i=0;i<s;i++){
printf("%d ",res[i]);
}
return 0;
}*/
//영역 구하기
/*#include<stdio.h>
int a[1001][1001]={};
int h[110][110]={};
void lake(int x,int y){
if(a[x][y]==0)return;
if(x<0 || y<0 ) return;
a[x][y]=0;
lake(x-1,y);
lake(x+1,y);
lake(x,y-1);
lake(x,y+1);
}
int main(){
int n,m=101,M=0;
scanf("%d",&n);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
scanf("%d",&h[i][j]);
if(h[i][j]>M)M=h[i][j];
if(h[i][j]<m)m=h[i][j];
}
}
int s,S=0;
for(int i=m;i<=M;i++){
s=0;
for(int j=0;j<n;j++){
for(int k=0;k<n;k++){
if(h[j][k]>=i)a[j][k]=1;
printf("%d ", a[j][k]);
}
printf("\n");
}
printf("\n");
for(int j=0;j<n;j++){
for(int k=0;k<n;k++){
if(a[j][k]==1){
lake(j,k);
s++;
}
}
}
if(s>S)S=s;
}
printf("%d",S);
return 0;
}*/
//안전 영역
/*# include<stdio.h>
int a[1002][1002]={};
int b[1002][1002]={};
int h,w,z=0,day=1;
int no(int x,int y){
if(x>h||y>w||x<=0||y<=0)return 0;
if(b[x][y]==1)return 1;
if(b[x][y]==0){
b[x][y]=-1;
return no(x-1,y)+no(x+1,y)+no(x,y-1)+no(x,y+1);
}
if(b[x][y]==-1)return 0;
}
void go(int x,int y){
if(a[x][y]==0){
a[x][y]=day;
z--;
}
}
int main(){
scanf("%d%d",&w,&h);
int yes=0;
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
scanf("%d",&a[i][j]);
b[i][j]=a[i][j];
if(a[i][j]==1)yes=1;
if(a[i][j]==0)z++;
}
}
if(yes==0){
printf("-1");
return 0;
}
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
if(b[i][j]==0){
if(no(i,j)==0){
printf("-1");
return 0;
}
}
}
}
for(day=0;z;day++){
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
if(a[i][j]==day-1){
go(i-1,j);
go(i,j-1);
go(i+1,j);
go(i,j+1);
}
}
}
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
printf("%d",a[i][j]);
}
printf("\n");
}
}
printf("%d",day-1);
}*/
//토마토(보류중)