/*
#include <stdio.h>
int main()
{
int arr[101][101] = {};
int h,w,n,l,d,x,y,i,j;
scanf("%d %d",&h,&w);
scanf("%d",&n);
for(i = 1; i <= n; i++)
{
scanf ("%d %d %d %d",&l,&d,&x,&y);
if(d == 0)
{
for(j = 0; j<l; j++)
{
arr[x][y+j] = 1;
}
}
else
{
for(j = 0; j<l; j++)
{
arr[x+j][y] = 1;
}
}
}
for (i = 1; i <= h; i++)
{
for (j = 1; j <= w; j++)
{
printf("%d ", arr[i][j]);
}
printf("\n");
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n;
int x=1,y,i,j;
int arr[51][51]= {};
scanf("%d", &n);
y=(n+1)/2;
arr[x][y]=1;
for(i=2; i<=n*n; i++)
{
if(i%n!=1)
{
if(--x==0)
{
x+=n;
}
if(--y==0)
{
y+=n;
}
arr[x][y]=i;
}
else
{
if (++x==n+1)
{
x%=n;
}
arr[x][y]=i;
}
}
for(i=1; i<=n; i++)
{
for(j=n; j>=1; j--)
{
printf("%d ", arr[i][j]);
}
printf("\n");
}
return 0;
}
*/
/*
#include <stdio.h>
int main ()
{
int arr [101][101]= {};
int n,i,j,x,y,k,sum=0;
scanf ("%d",&n);
for(k=1; k<=n; k++)
{
scanf ("%d %d",&x,&y);
for (i=x; i<x+10; i++)
{
for (j=y; j<y+10; j++)
{
arr[i][j]=1;
}
}
}
for (i=1; i<=100; i++)
{
for (j=1; j<=100; j++)
{
sum=sum+arr[i][j];
}
}
printf ("%d", sum);
return 0;
}
*/
/*
#include <stdio.h>
int main ()
{
int arr [101][101]={};
int n,i,j,x,y,x1,y1,k,sum=0;
for (k=1;k<=4;k++)
{
scanf ("%d %d %d %d",&x,&y,&x1,&y1);
for (i=x;i<x1;i++)
{
for (j=y;j<y1;j++)
{
arr[i][j]=1;
}
}
}
for (i=0;i<100;i++)
{
for (j=0;j<100;j++)
{
sum=sum+arr[i][j];
}
}
printf ("%d",sum);
return 0;
}
*/
/*
#include <stdio.h>
int main ()
{
int arr[100001]= {};
int n,i,j,k,sum=0,max=-10000000;
scanf ("%d %d",&n,&k);
for (i=1; i<=n; i++)
{
scanf ("%d",&arr[i]);
}
for (i=1; i<=n-k+1; i++)
{
sum=0;
for (j=i; j<i+k; j++)
{
sum=sum+arr[j];
}
if(sum>max)
{
max=sum;
}
}
printf ("%d",max);
return 0;
}
#include <stdio.h>
#include <string.h>
int main()
{
char str[100]={};
// scanf("%s",str);
gets(str);
printf("%d\n",strlen(str));
printf("%s",str);
return 0;
}
*/
/*
#include <stdio.h>
#include <string.h>
int main()
{
char[100]={};
scanf ("%c",str);
printf ("%c",str);
return 0;
}
*/
/*
#include <stdio.h>
#include <string.h>
int main ()
{
char str[9]={};
scanf ("%s",str);
printf ("%s",str);
return 0;
}
*/
/*
#include <stdio.h>
#include <string.h>
int main ()
{
char str [31]={};
gets(str);
printf ("%s",str);
return 0;
}
*/
/*
#include <stdio.h>
#include <string.h>
int main ()
{
char str[11]={};
int i;
scanf ("%s",str);
for (i=0;i<strlen(str);i++)
{
if(str[i]=='t')
{
printf("%d ",i+1);
}
}
return 0;
}
*/
/*
#include <stdio.h>
#include <string.h>
int main ()
{
char str1[21]={},str2[21]={},str3[21]={};
scanf ("%s %s %s",str1, str2 , str3);
if(str1[strlen(str1)-1]==str2[0]
&&str2[strlen(str2)-1]==str3[0]
&&str3[strlen(str3)-1]==str1[0])
{
printf ("good");
}
else
{
printf ("bad");
}
return 0;
}
*/
/*
#include <stdio.h>
#include <string.h>
int main ()
{
char str[100001]={};
int i,cnt=0,cnt1=0;
scanf ("%s",str);
for (i=0;i<strlen(str);i++)
{
if(str[i]=='(')
{
cnt++;
}
else
{
cnt1++;
}
}
printf ("%d %d",cnt,cnt1);
return 0;
}
*/
/*
#include <stdio.h>
#include <string.h>
int main()
{
char str [100]= {};
scanf ("%s",str);
if (str[0]=='l'&& str[1]=='o'&& str[2]=='v'&& str[3]=='e'&&str[4]=='\0')
{
printf ("I love you.");
}
return 0;
}
int main ()
{
char str [101]={};
// scanf ("%s",str);
printf("%c",'t'-32);
}
*/
/*
#include <stdio.h>
#include <string.h>
int main ()
{
char str [1001]= {};
int i;
scanf ("%s",str);
for (i=0; i<strlen(str); i++)
{
if ('a'<=str[i]&& str[i]<='z')
{
printf ("%c",str[i]-32);
}
else if('A'<=str[i]&& str[i]<='Z')
{
printf ("%c",str[i]+32);
}
else
{
printf ("%c",str[i]);
}
}
return 0;
}
*/
/*
#include <stdio.h>
#include <string.h>
int main ()
{
char str [21]= {};
int i;
scanf ("%s",str);
for (i=0; i<strlen(str); i++)
{
printf ("%c",str[i]+2);
}
printf ("\n");
for (i=0; i<strlen(str); i++)
{
printf ("%c",(str[i]*7)%80+48);
}
return 0;
}
*/