/*
#include <stdio.h>
#include <stdlib.h>
int main()
{
printf("Hello world!\n");
return 0;
}
*/
/*
#include<stdio.h>
int main(){
int a[27][27]={0};
int b[27][27]={0};
int i,j,x,y,sum=0;
for(i=1; i<=25; i++){
for(j=1; j<=25; j++){
scanf("%d", &a[i][j]);
}
}
for(i=1; i<=25; i++){
for(j=1; j<=25; j++){
sum=0;
for(x=i-1; x<=i+1; x++) {
for(y=j-1; y<=j+1; y++) {
sum += a[x][y];
}
}
if(a[i][j]==0&&sum==3){
b[i][j]=1;
}
else if(a[i][j]==1&&(sum>=5||sum<=2)){
b[i][j]=0;
}
else if(a[i][j]==1&&(sum==3||sum==4)){
b[i][j]=1;
}
}
}
for(i=1; i<=25; i++){
for(j=1; j<=25; j++){
printf("%d ", b[i][j]);
}
printf("\n");
}
}
*/
/*
#include<stdio.h>
int main()
{
int c[170][170]= {0};
int d[170][170]= {0};
int i,j,x,y,z,k,a,b,e,f,pp,sum=0;
scanf("%d %d", &a, &b);
scanf("%d %d %d", &x, &y, &z);
for(i=1; i<=a; i++)
{
for(j=1; j<=b; j++)
{
scanf("%d", &c[i][j]);
}
}
scanf("%d", &k);
for(pp=0; pp<k; pp++)
{
for(i=1; i<=a; i++)
{
for(j=1; j<=b; j++)
{
sum=0;
for(e=i-1; e<=i+1; e++)
{
for(f=j-1; f<=j+1; f++)
{
sum += c[e][f];
}
}
if(c[i][j]==0&&sum==x)
{
d[i][j]=1;
}
else if(c[i][j]==1&&sum>=z+1)
{
d[i][j]=0;
}
else if(c[i][j]==1&&sum>=y+1)
{
d[i][j]=1;
}
}
}
for(i=1; i<=a; i++)
{
for(j=1; j<=b; j++)
{
c[i][j] = d[i][j];
d[i][j] = 0;
}
}
}
for(i=1; i<=a; i++)
{
for(j=1; j<=b; j++)
{
printf("%d ", c[i][j]);
}
printf("\n");
}
}
*/
/*
#include<stdio.h>
int main()
{
int a[11][11]={0};
int i,j,r,c,sum=0;
for(i=1; i<=9; i++)
{
for(j=1; j<=9; j++)
{
scanf("%d", &a[i][j]);
}
}
scanf("%d %d", &r, &c);
if(a[r][c]==1)
{
printf("-1");
}
else
{
sum += a[r-1][c]+a[r-1][c-1]+a[r-1][c+1]+a[r][c+1]+a[r+1][c+1]+a[r+1][c]+a[r+1][c-1]+a[r][c-1];
printf("%d", sum);
}
}
*/
/*
#include<stdio.h>
int sum(int x, int y);
int main() {
int a, b, c;
scanf("%d %d", &a, &b);
c = sum(a, b);
printf("%d", c);
}
int sum(int x, int y){
return x+y;
}
*/
/*
#include<stdio.h>
void f(){
printf("hello\n");
return;
}
int main(){
f();
return 0;
}
*/
/*
#include<stdio.h>
void f(){
printf("%d", 123);
return;
}
int main(){
f();
return 0;
}
*/
/*
#include<stdio.h>
void f(){
printf("%c",'*');
return;
}
int main(){
f();
return 0;
}
*/
/*
#include<stdio.h>
void f(){
for(int i=1; i<=2; i++){
printf("%c", '*');
}
return;
}
int main(){
f();
return 0;
}
*/
/*
#include<stdio.h>
char f(){
return 'A';
}
int main(){
printf("%c", f());
return 0;
}
*/
/*
#include<stdio.h>
int i, n, d[100010], k;
int f(int k){
int i;
for(i=1; i<=n; i++){
if(k==d[i]){
return i;
}
}
return -1;
}
int main(){
scanf("%d", &n);
for(i=1; i<=n; i++){
scanf("%d", &d[i]);
}
scanf("%d", &k);
printf("%d\n", f(k));
}
*/
/*
#include<stdio.h>
double x;
long long int f(double x){
long long int t=(long long int)x;
if(t<x)
return x+1;
else
return x;
}
int main(){
scanf("%lf", &x);
printf("%lld\n", f(x));
}
*/