/*
#include <stdio.h>
#include <string.h>
char stack[201];
int top=-1;
void push(char a)
{
stack[++top]=a;
}
char pop()
{
if(top==-1) return -1;
return stack[top--];
}
int GetOpPrec(char op)
{
switch(op)
{
case '*':
case '/':
return 5;
case '+':
case '-':
return 3;
case '(':
return 1;
}
return -1;
}
int whoPrecOp(char op1,char op2)
{
int op1Prec = GetOpPrec(op1);
int op2Prec = GetOpPrec(op2);
if(op1Prec>op2Prec) return 1;
else if(op1Prec<op2Prec) return -1;
else return 0;
}
int conv(char a[])
{
int i,idxE=0;
char convexp[200]={},tok;
for(i=0;i<=200;i++){
tok=a[i];
if(isdigit(tok)) convexp[idxE++]=tok;
else
{
switch(tok)
{
case '(':
break;
case ')':
while(top!=-1)
{
convexp[idxE++]=pop();
}
pop();
break;
case '+':
case '-':
case '*':
case '/':
if(whoPrecOp(stack[top-1],tok)>=0)
convexp[idxE++]=pop();
push(tok);
break;
}
}
}
while(top!=-1) convexp[idxE++]=pop();
strcpy(a, convexp);
}
int main()
{
char a[200]={};
scanf("%s",a);
conv(a);
printf("%s",a);
}
*/
/*
switch(tok)
{
case '(':
push(tok);
break;
case ')':
while(1)
{
if(stack[top]='(')
break;
convexp[idxE++]=pop();
}
case '+':
case '-':
case '*':
case '/':
push(tok);
break;
#include <stdio.h>
int stack[200];
int top=-1;
void push(int a)
{
stack[++top]=a;
}
int pop()
{
if(top==-1)return -1;
return stack[top--];
}
void c(char a)
{
int op2=pop();
int op1=pop();
switch(a)
{
case '+':
push(op1+op2);
break;
case '-':
push(op1-op2);
break;
case '*':
push(op1*op2);
break;
case '/':
push(op1/op2);
break;
}
}
int main()
{
char a[200]={};
int i,temp=0;
gets(a);
for(i=0;i<200;i++)
{
if(a[i]=='\0'||a[i]==' ')continue;
if(isdigit(a[i]))
{
if(temp!=0){
temp*=10;
temp+=a[i]-'0';
}
else
{
temp+=a[i]-'0';
}
if(!isdigit(a[i+1])){
push(temp);
temp=0;
}
}
else
{
c(a[i]);
}
}
printf("%d",pop());
}
*/
/*
#include <stdio.h>
#define SIZE 4
int queue[SIZE];
int front=0, rear=0;
//front : 마지막으로 나간 데이터의 위치
//rear : 마지막으로 입력된 데이터의 위치 (top)
void enq(int data)
{
if((rear+1)%SIZE==front) return ; //full check
rear=(rear+1)%SIZE;
queue[rear]=data;
}
int deq()
{
if(front==rear) return -1; //empty check
front=(front+1)%SIZE;
return queue[++front];
}
*/
/*
#include <stdio.h>
int memo[101]= {0};
int c,e,map[101][101]= {0};
void dfs(int node)
{
memo[node]=1;
for(int i=1; i<=c; i++)
{
if(map[node][i]==1&&memo[i]!=1)
{
dfs(i);
}
}
}
int main()
{
int i,j;
scanf("%d\n%d",&c,&e);
for(int k=0; k<e; k++)
{
scanf("%d %d",&i,&j);
map[i][j]=1;
map[j][i]=1;
}
dfs(1);
j=0;
for(i=2; i<=c; i++)
{
j+=memo[i];
}
printf("%d",j);
}
*/
//4421
/*
#include<stdio.h>
int map[25][25]={0};
int d[26]={0};
int k=0;
void dfs(int x, int y,int n)
{
if(x<0||y<0||x>=n||y>=n||map[x][y]!=1) return ;
map[x][y]=0;
d[k]++;
dfs(x+1,y,n);
dfs(x-1,y,n);
dfs(x,y+1,n);
dfs(x,y-1,n);
}
int main()
{
int i,j,n,temp;
scanf("%d",&n);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%1d",&map[i][j]);
}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(map[i][j]==1)
{
k++;
dfs(i,j,n);
}
}
}
for(i=1;i<k;i++)
{
for(j=1;j<=k-i;j++)
{
if(d[j]>d[j+1])
{
temp=d[j];
d[j]=d[j+1];
d[j+1]=temp;
}
}
}
printf("%d\n",k);
for(i=1;i<=k;i++)printf("%d\n",d[i]);
}
*/
/*
#include<stdio.h>
int map[7][7],c=0,d[6]={0},sum=0;
void dfs(int x,int y,int n)
{
if(x<0||y<0||x>=7||y>=7||map[x][y]!=n) return;
map[x][y]=0;
c++;
if(c>=3){
c=-100;
d[n]+=1;
}
dfs(x+1,y,n);
dfs(x-1,y,n);
dfs(x,y+1,n);
dfs(x,y-1,n);
}
int main()
{
int i,j,n=1;
for(i=0;i<7;i++){
for(j=0;j<7;j++)
scanf("%d",&map[i][j]);
}
for(i=0;i<7;i++)
{
for(j=0;j<7;j++)
{
if(map[i][j]!=0)
{
n=map[i][j];
c=0;
dfs(i,j,n);
}
}
}
for(i=1;i<6;i++)
sum+=d[i];
printf("%d",sum);
return;
}
*/
//4024
/*
#include<stdio.h>
char map[100][100]={0};
int w,h;
void dfs(int x,int y)
{
if(x<0||y<0||x>=h||y>=w||map[x][y]!='L') return;
map[x][y]='.';
dfs(x+1,y);
dfs(x-1,y);
dfs(x,y+1);
dfs(x,y-1);
dfs(x+1,y+1);
dfs(x-1,y+1);
dfs(x+1,y-1);
dfs(x-1,y-1);
}
int main()
{
int i,j,c=0;
scanf("%d %d",&w,&h);
for(i=0;i<h;i++)
{
for(j=0;j<w;j++)
scanf(" %c",&map[i][j]);
}
for(i=0;i<h;i++){
for(j=0;j<w;j++){
if(map[i][j]=='L'){
c++;
dfs(i,j);
}
}
}
printf("%d",c);
return 0;
}*/
//4572
/*
#include <stdio.h>
int map[100][100]={0},m,n,d[101]={0},num;
void dfs(int x,int y)
{
if(x<0||y<0||x>=m||y>=n||map[x][y]!=0)return;
map[x][y]=1;
d[num]++;
dfs(x+1,y);
dfs(x-1,y);
dfs(x,y-1);
dfs(x,y+1);
}
int main()
{
int k,x,i,j,x1,x2,y1,y2,c=0,temp;
scanf("%d %d %d",&m,&n,&k);
for(i=1;i<=k;i++){
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
for(j=y1;j<y2;j++){
for(x=x1;x<x2;x++)
map[j][x]=1;
}
}
for(i=0;i<m;i++){
for(j=0;j<n;j++)
if(map[i][j]==0){
num++;
dfs(i,j);
}
}
for(i=1;i<=num;i++){
for(j=1;j<=num-i;j++){
if(d[j]>d[j+1]){
temp=d[j];
d[j]=d[j+1];
d[j+1]=temp;
}
}
}
printf("%d\n",num);
for(i=1;i<=num;i++)
printf("%d ",d[i]);
}
*/
//4697
/*
#include <stdio.h>
#include <string.h>
int mapt[101][101],map[101][101],n;
void copymap()
{
int i, j;
for(i=0;i<n;i++)
for(j=0;j<n;j++){
map[i][j]=mapt[i][j];
}
}
void dfs(int x,int y,int h)
{
if(x<0||y<0||x>=n||y>=n||map[x][y]<=h)return;
map[x][y]=0;
dfs(x+1,y,h);
dfs(x-1,y,h);
dfs(x,y-1,h);
dfs(x,y+1,h);
}
int main()
{
int i,j,c=0,h=1,max=0;
scanf("%d",&n);
for(i=0;i<n;i++)
for(j=0;j<n;j++){
scanf("%d",&mapt[i][j]);
map[i][j]=mapt[i][j];
}
while(h<101){
copymap();
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(map[i][j]>h){
c++;
dfs(i,j,h);
}
}
}
if(max<=c)
max=c;
c=0;
h++;
}
printf("%d",max);
}
*/