//import java.util.*;
//import java.util.Arrays;
//public class Main
//{
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
// int f = t.nextInt();
// int c = t.nextInt();
// int cf = 0;
// int arr[] = new int[f];
// for(int i=0; i<f; i++)
// {
// arr[i] = t.nextInt();
// }
// Arrays.sort(arr);
// for(int i=0; i<f; i++)
// {
// if(cf != c) {System.out.printf("%d ",arr[i]);}
// else if(cf == c)
// {
// System.out.println();
// System.out.printf("%d ", arr[i]);
// cf=0;
// }
// cf++;
// }
// }
//
//
// }
//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];
// for(int i=0; i<n; i++)
// {
// arr[i] = t.nextInt();
// }
// for(int i=0; i<n; i++)
// {
// System.out.printf("%d: ", i+1);
// for(int j=0; j<n; j++)
// {
// if(i==j)
// {
// continue;
// }
// else
// {
// if(arr[i]>arr[j])
// {
// System.out.printf("> ");
// }
// else if(arr[i]<arr[j])
// {
// System.out.printf("< ");
// }
// else if(arr[i]==arr[j])
// {
// System.out.printf("= ");
// }
// }
// }
// System.out.println();
// }
// }
//}
/*
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner t = new Scanner(System.in);
int a = t.nextInt();
int[] b = new int[a];
for (int i = 0; i < a; i++) {
b[i] = t.nextInt();
}
for (int i = 0; i < a; i++) {
for (int j = i; j < a; j++) {
System.out.print(b[j]+ " ");
}
for (int j = 0; j < i; j++) {
System.out.print(b[j] + " ");
}
System.out.println();
}
}
}
*/
//import java.util.*;
//public class Main
//{
// public static void main(String[] args)
// {
// char arr[] = new char[50];
// String str = "hello world";
//
// arr = str.toCharArray();
//
// System.out.println(str);
//
// //str[10] (x)
// //str.charAt(10)
// //arr[10]
//
// String str1 = "hello";
// String str2 = "world";
// //if(str1.equals(str2)) (o)
// //if(str1==str2) (x)
//
// //if(str1.charAt(2)=='a') (o)
// }
//}
//import java.util.*;
//public class Main
//{
// public static void main(String[] args)
// {
// Scanner t = new Scanner(System.in);
// String str;
// str = t.nextLine();
//
// for(int i=0; i<str.length(); i++)
// {
// System.out.printf("\'%c\'", str.charAt(i));
// System.out.println();
// }
// }
//}
//import java.util.*;
//public class Main
//{
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
// String str;
// str = t.nextLine();
// System.out.println(str);
// }
//}
//import java.util.*;
//public class Main
//{
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
// String str;
// str = t.nextLine();
// System.out.println(str);
// }
//}
//import java.util.*;
//public class Main
//{
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
// String str;
// str = t.nextLine();
// System.out.println(str);
// }
//}
//import java.util.*;
//public class Main
//{
// public static void main(String[] args)
// {
// Scanner t = new Scanner(System.in);
// String str = t.nextLine();
// char[] b = str.toCharArray();
// for(int i=0; i<b.length; i++)
// {
// int x = (int)b[i];
// if('A' <= x && x<=90)
// {
// b[i]+=32;
// }
// else if(97<=x && x<=122)
// {
// b[i]-=32;
// }
// }
//
// for (int i = 0; i < b.length; i++) {
// System.out.print(b[i]);
// }
// }
//}
//import java.util.*;
//public class Main
//{
// public static void main(String[] args)
// {
// Scanner t = new Scanner(System.in);
// String str = t.nextLine();
// char[] b = str.toCharArray();
// if( b.length == 4&& b[0] == 'l' && b[1] == 'o' && b[2] == 'v' && b[3] == 'e')
// {
// System.out.println("I love you.");
// }
// }
//}
import java.util.*;
public