//import java.util.*;
//
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// int arr[][] = new int [30][30];
// for(int i=1; i<20; i++) {
// for(int j=1; j<20; j++) {
// arr[i][j] = t.nextInt();
// }
// }
//
// int k = t.nextInt();
// for(int i=0; i<k; i++) {
// int x = t.nextInt();
// int y = t.nextInt();
//
// for(int j=1; j<20; j++) {
// arr[x][j] = arr[x][j]==1 ? 0 : 1;
// // wid
// }
// for(int j=1;j<20; j++) {
// arr[j][y] = arr[j][y]==1 ? 0 : 1;
// // hei
// }
// }
// for(int i=1; i<20; i++) {
// for(int j=1; j<20; j++) {
// System.out.print(arr[i][j]+" ");
// }
// System.out.println();
// }
// }
//}
//import java.util.*;
//
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// int arr[][] = new int [100][100];
// int w = t.nextInt();
// int h = t.nextInt();
//
// int n = t.nextInt();
// for(int i=0; i<n; i++) {
// int l = t.nextInt();
// int d = t.nextInt();
// int x = t.nextInt();
// int y = t.nextInt();
//
// for(int j=0;j<l;j++) {
// if(d==1) {
// arr[x+j][y] = 1;
// }
// else if(d==0) {
// arr[x][y+j] = 1;
// }
// }
// }
// for(int i=1; i<=w; i++) {
// for(int j=1; j<=h;j++) {
// System.out.print(arr[i][j]+ " ");
// }
// System.out.println();
// }
// }
//}
//import java.util.*;
//
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// int arr[][] = new int [100][100];
// int x=1;
// int y=1;
// for(int i=0;i<10;i++) {
// for(int j=0;j<10;j++) {
// arr[i][j] = t.nextInt();
// }
// }
// arr[1][1] = 9;
// for(int i=0;;i++) {
//
// if(arr[x][y+1]==2) {
// arr[x][y+1] = 9;
// break;
// }
// else if(arr[x][y+1]==1&&arr[x+1][y]==2) {
// arr[x+1][y] = 9;
// break;
// }
// else if(arr[x][y+1]==1&&arr[x+1][y]==1) {
// break;
// }
// else if(arr[x][y+1]==1) {
// x++;
// arr[x][y] = 9;
// }
// else {
// y++;
// arr[x][y] = 9;
// }
// }
// for(int i=0;i<10;i++) {
// for(int j=0;j<10;j++) {
// System.out.print(arr[i][j]+ " ");
// }
// System.out.println();
// }
//
// }
//}