//import java.util.*;
//public class Main
//{
// public static void main(String[] args)
// {
// Scanner t = new Scanner(System.in);
// int map[][] = new int [100][100];
// int x = t.nextInt();
// int y = t.nextInt();
//
// for(int i=0; i<x; i++)
// {
// for(int j=0; j<y; j++)
// {
// map[i][j] = 0;
// }
// }
//
// int data[][] = new int[10][4];
// int n = t.nextInt();
// for(int i=0; i<n; i++)
// {
// for(int j=0; j<4; j++)
// {
// data[i][j] = t.nextInt();
// }
// }
//
// for(int i=0; i<n; i++)
// {
// if(data[i][1] == 1)
// {
// for(int j = 0; j<data[i][0]; j++)
// {
// map[ data[i][2]-1 + j] [ data[i][3]-1 ] = 1;
// }
// }
// else if(data[i][1] == 0)
// {
// for(int j=0; j<data[i][0]; j++)
// {
// map[ data[i][2]-1] [ data[i][3]-1 + j] = 1;
// }
// }
// }
//
// for(int i=0; i<x; i++)
// {
// for(int j=0; j<y; j++)
// {
// System.out.print(map[i][j]+" ");
// }
// System.out.println();
// }
// }
//}
//import java.util.*;
//public class Main
//{
// public static void main(String[] args)
// {
// Scanner t = new Scanner(System.in);
// int map[][] = new int [11][11];
// int x=2;
// int y=2;
// int first = 1;
// for(int i = 1; i<=10; i++)
// {
// for(int j = 1; j<=10; j++)
// {
// map[i][j] = t.nextInt();
// }
// }
//
// while(true)
// {
// if(first == 1)
// {
// if(map[x][y] == 2)
// {
// map[x][y]=9;
// break;
// }
// else if(map[x][y] == 1)
// {
// break;
// }
// else if(map[x][y] == 0)
// {
// map[x][y] = 9;
// first = 0;
// }
// }
// else
// {
// if(map[x][y+1] == 0)
// {
// map[x][y+1] = 9;
// y+=1;
// continue;
// }
// else if(map[x][y+1] == 2)
// {
// map[x][y+1] = 9;
// break;
// }
// else if(map[x+1][y] == 2)
// {
// map[x+1][y] = 9;
// break;
// }
// else if(map[x][y+1] == 1)
// {
// if(map[x+1][y] == 1)
// {
// break;
// }
// else if(map[x+1][y] == 0)
// {
// map[x+1][y] = 9;
// x+=1;
// continue;
// }
// }
// }
// }
//
// for(int i=1; i<=10; i++)
// {
// for(int j=1; j<=10; j++)
// {
// System.out.print(map[i][j] + " ");
// }
// System.out.println();
// }
// }
//}
//import java.util.*;
//public class Main
//{
// public static void main(String[] args)
// {
// Scanner t = new Scanner(System.in);
// int map[][] = new int [20][20];
// int player[][] = new int [10][5];
// int bomb;
// int mx = 1;
// int px = 1;
// int my = 1;
// int py = 1;
// for(int i=1; i<=10; i++)
// {
// for(int j=1; j<=10; j++)
// {
// map[i][j]=t.nextInt();
// }
// }
// for(int i=1; i<=10; i++)
// {
// for(int j=1; j<10; j++)
// {
// if(map[i][j] > 0)
// {
// bomb = map[i][j]+2;
// py = 1;
// my= 1;
// px= 1;
// mx= 1;
// map[i][j] = -2;
// for(int k=1; k<bomb; k++)
// {
// if(i-k >=0 && j-k>=0)
// {
// if(px == 1 && map[i+k][j] != -1) {map[i+k][j] = -2;}
// else {px = 0;}
// if(mx == 1 && map[i-k][j] != -1) {map[i-k][j] = -2;}
// else {mx = 0;}
// if(py == 1 && map[i][j+k] != -1) {map[i][j+k] = -2;}
// else {py = 0;}
// if(my == 1 && map[i][j-k] != -1) {map[i][j-k] = -2;}
// else {my = 0;}
// }
// }
// }
// }
// }
////폭탄 터트리기 끝
//
// int n=t.nextInt();
// for(int i=1; i<=n; i++)
// {
// for(int j=0; j<2; j++)
// {
// player[i][j] = t.nextInt();
// }
// }
// for(int i=1; i<=n; i++)
// {
// if(map[ player[i][0] ][ player[i][1] ] == 0)
// {
// map[ player[i][0] ][ player[i][1] ] = i;
// }
// }
//
// for(int i=1; i<=10; i++)
// {
// for(int j=1; j<=10; j++)
// {
// System.out.print(map[i][j] + " ");
// }
// System.out.println();
// }
// System.out.println("Character Information");
// for(int i=1; i<=n; i++)
// {
// if(map[ player[i][0] ][ player[i][1] ] == i)
// {
// System.out.println("player " + i + " survive");
// }
// else
// {
// System.out.println("player " + i + " daed");
// }
// }
// }
//}