//import java.util.*;
//public class Main {
// public static void main(String[] args) {
// int j, i;
// int x, y, n;
// int arr[][] = new int[20][20];
// Scanner t = new Scanner(System.in);
// for(i=1; i<=19; i++) {
// for(j=1; j<=19; j++) {
// arr[i][j] = t.nextInt();
// }
// }
// n = t.nextInt();
// for(i=1; i<=n; i++) {
// x = t.nextInt();
// y =t.nextInt();
// for(j=1; j<=19; j++) {
// if(arr[x][j]==0)
// arr[x][j]=1;
// else arr[x][j]=0;
// }
// for(j=0; j<=19; j++) {
// if(arr[j][y]==0) arr[j][y]=1;
// else arr[j][y]=0;
// }
// }
// for(i=1; i<=19; i++) {
// for(j=1; j<=19; j++) {
// System.out.printf("%d ", arr[i][j]);
// }
// System.out.println();
// }
// }
//}
// System.out.printf("%d(%d,%d)\t", map[i][j], i, j);
//import java.util.*;
//public class Main {
// public static void main(String[] args) {
// //i가 세로 j가 가로
// Scanner t = new Scanner(System.in);
// int n = t.nextInt();
// int map[][] = new int[n][n];
//
// int k = 1;
// for(int i=0; i<n; i++) {
// for(int j=0; j<n; j++) {
// map[i][j] = k++;
// }
// }
// for(int i=0; i<n; i++) {
// for(int j=0; j<n; j++) {
// System.out.printf("%d ", 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 n = t.nextInt();
// int map[][] = new int[n][n];
//
// int k = 1;
// for(int i=0; i<n; i++) {
// for(int j=0; j<n; j++) {
// map[i][j] = k++;
// }
// }
// for(int i=0; i<n; i++) {
// for(int j=n-1; j>=0; j--) {
// System.out.printf("%d ", 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 n = t.nextInt();
// int map[][] = new int[n][n];
// //i가 세로 j가 가로
// int k = 1;
// for(int i=0; i<n; i++) {
// for(int j=0; j<n; j++) {
// map[i][j] = k++;
// }
// }
// for(int i=0; i<n; i++) {
// for(int j=0; j<n; j++) {
// System.out.printf("%d ", map[j][i]);
// }
// System.out.println();
// }
// }
//
// }
//import java.util.*;
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
// int n = t.nextInt();
// int map[][]= new int[n][n];
// int k = 1;
// for(int i=0; i<n; i++) {
// for(int j=0; j<n; j++) {
// map[i][j] = k++;
// }
// }
// for(int i=n-1; i>=0; i--) {
// for(int j=0; j<n; j++) {
// System.out.printf("%d ", map[j][i]);
// }
// System.out.println();
// }
// }
//}
//import java.util.*;
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
// int n = t.nextInt(); //n은 세로
// int m = t.nextInt(); //m은 가로
// int map[][] = new int[n][m];
// int k = 1;
// for(int i=0; i<n; i++) {
// for(int j=0; j<m; j++) {
// map[i][j] = k++;
// }
// }
// for(int i=n-1; i>=0; i--) {
// for(int j=m-1; j>=0; j--) {
// System.out.printf("%d ", 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 n = t.nextInt();
// int m = t.nextInt();
// int map[][] =new int[n][m];
// int k=1;
// for(int i=0; i<n; i++) {
// for(int j=0; j<m; j++) {
// map[i][j] = k++;
// }
// }
// for(int i=n-1; i>=0; i--) {
// for(int j=0; j<m; j++) {
// System.out.printf("%d ", 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 n = t.nextInt();
// int m = t.nextInt();
// int map[][] = new int[n][m];
// int k=1;
// for(int j=0; j<m; j++) {
// for(int i=n-1; i>=0; i--) {
// map[i][j]= k++;
// }
// }
// for(int i=0; i<n; i++) {
// for(int j=m-1; j>=0; 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 n = t.nextInt();
// int m = t.nextInt();
// int map[][] = new int[n][m];
// int k=1;
// for(int j=0; j<m; j++) {
// for(int i=0; i<n; i++) {
// map[i][j]= k++;
// }
// }
// for(int i=0; i<n; i++) {
// for(int j=m-1; j>=0; j--) {
// System.out.printf("%d ", map[i][j]);
// }
// System.out.println();
// }
// }
//}