//190815
//import java.util.*;
//
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// int a = t.nextInt();
// int arr[] = new int[32];
// int k=0;
// for(int i=0; i<32; i++) {
// arr[i] = a%2;
// a/=2;
// if(a==0) break;
// k++;
// }
//
// for(int i=k; i>=0; i--) {
// System.out.print(arr[i]);
// }
// }
//}
//import java.util.*;
//
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// String str = t.next();
//
// for(int i=0; i<str.length(); i++) {
// if(str.charAt(i)=='t') {
// System.out.print((i+1)+" ");
// }
// }
// }
//}
//import java.util.*;
//
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// String str = t.next();
//
// System.out.println("welcome!"+" "+str);
// }
//}
//import java.util.*;
//
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// String a = t.next();
// String b = t.next();
// String c = t.next();
//
// if(b.charAt(0)==a.charAt(a.length()-1) &&c.charAt(0)==b.charAt(b.length()-1)&&a.charAt(0)==c.charAt(c.length()-1)) {
// System.out.println("good");
// }
// else {
// System.out.println("bad");
// }
//
// }
//}
//import java.util.*;
//
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// int n = t.nextInt();
// int arr[][] = new int[n][n];
// int k = 1;
//
// 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 arr[][] = new int [n][n];
// int k = 1;
//
// for(int i = 0; i<n; i++) {
// for(int j = 0; j<n; j++) {
// arr[i][j] = k++;
// 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 arr[][] = new int [n][n];
// int k = 1;
//
// 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 arr[][] = new int [n][m];
// int k = 1;
//
// for(int i = 0; i<n;i++) {
// for(int j = 0; j<m;j++) {
// arr[i][j] = k++;
// }
// }
// for(int i = n-1; i>=0; i--) {
// for(int j = m-1; j>=0; 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 m = t.nextInt();
// int arr[][] = new int [n][m];
// int k = 1;
//
//
// for(int j = 0; j<m; j++) {
// for(int i = 0; i<n;i++) {
// arr[i][j] = k++;
// }
// }
// for(int i = n-1; i>=0; i--) {
// for(int j = m-1; j>=0;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 arr[][] = new int[n][n];
// int k = 1;
//
// 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++) {
// if(i%2==0) {
// for(int j=0; j<n; j++) {
// System.out.print(arr[i][j] +" ");
// }
// }
// else {
// for(int j=n-1; j>=0; 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 arr[][] = new int[n][n];
// int k = 1;
//
// for(int i=0;i<n;i++) {
// if(i%2==0) {
// for(int j=0;j<n;j++) {
// arr[i][j] = k++;
// }
// }
// else {
// for(int j=n-1; j>=0;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();
// }
// }
//}