//import java.util.*;
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// int n = t.nextInt();
// int k=1;
//
// int arr[][] = new int [n][n];
//
// for(int i=0; i<n; i++) {
// for(int j=0; j<n; j++) {
// arr[i][j] = k++;
// }
// }
//
// for(int i=0; i<n; i++) {
// for(int j=0; j<n; 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 n = t.nextInt();
// int k=1;
//
// int arr[][] = new int [n][n];
//
// for (int i=0; i<n; i++){
// for (int j=0; j<n; j++) {
// arr[i][j] = k++;
// }
// }
// for(int i=0; i<n; i++) {
// for(int j=0; j<n; j++) {
// System.out.print(arr[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 m = t.nextInt();
// int k = n*m;
//
// int a[][] = new int [n][m];
//
// for (int i=0; i<n; i++) {
// for (int j=0; j<m; j++) {
// a[i][j] = k--;
// }
// }
// for (int i=0; i<n; i++) {
// for (int j=0; j<m; j++) {
// System.out.print(a[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 k = n*m;
//
// int a [][] = new int [n][m];
//
// for (int i=0; i<m; i++) {
// for (int j=0; j<n; j++) {
// a[j][i] = k--;
// }
// }
// for (int i=0; i<n; i++) {
// for (int j=0;j<m; j++) {
// System.out.print(a[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 a[][] = new int [n][n];
//
// for(int i=0; i<n; i++) {
// a[i][0] = t.nextInt();
// }
//
// for (int i=1; i<n; i++) {
// for (int j=1; j<=i; j++) {
// a[i][j] = a[i][j-1] - a[i-1][j-1];
// }
// }
// for (int i=0; i<n; i++) {
// for (int j=0; j<=i; j++) {
// System.out.print(a[i][j]+" ");
// }
// System.out.println();
// }
// }
//}
//import java.util.*;
//public class Main {
// public static void main(String[] args) {
// Scanner t= new Scanner(System.in);
//
//
// int a[][] = new int [11][10];
//
// for(int i=0; i<a.length; i++) {
// for(int j=0; j<a[i].length; j++) {
// a[i][j] = t.nextInt();
// }
// }
//
// for (int j=0; j<10; j++) {
// if (a[10][j]>0) {
// int i=9;
// for (i=9; i>=0; i--) {
// if (a[i][j]>0) {
// System.out.println(j+1 +" crash");
// break;
// }
// else if (a[i][j]<0) {
// System.out.println(j+1+" fall");
// break;
// }
// }
// if (i==-1) {
// System.out.println(j+1+" safe");
// }
// }
// }
//
// }
//}
//import java.util.*;
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// int n = t.nextInt();
// int x=0;
// int y=n/2;
// int a[][] = new int [n][n];
//
//
// for(int k=1; k<=n*n; k++) {
// a[x][y] = k;
//
// if (k%n!=0) {
// if (x==0) {
// x=n-1;
// }
// else
// {
// x--;
//
// }
// if (y==n-1) {
// y=0;
// }
// else
// {
// y++;
// }
// }
// else {
// x++;
// }
// }
//
// for(int i=0; i<n; i++) {
// for(int j=0; j<n; j++) {
// System.out.print(a[i][j] +" ");
// }
// System.out.println();
// }
// }
//}