//190810
//import java.util.*;
//
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// int n = t.nextInt();
// int k = t.nextInt();
// for(int i=0;i<n;i++) {
//
// for(int j=0; j<n; j++) {
//// if(i==0||j==0||i==n-i||j==n-i||j+1==n-i||j+1+k==n-i||j+i-(2*k)==n-i||j+1-(3*k)==n-i)
// if(i==0||j==0||i==n-1||j==n-1||(i+j+1)%k==0)
// System.out.print("*");
// else {
// System.out.print(" ");
//
// }
// }
// 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];
//
// for(int i=0; i<n; i++) {
// arr[i] = t.nextInt();
// }
// System.out.println(arr.length+"^A^");
//
// for(int i=0; i<n; i++) {
// System.out.println(arr[i] + " ");
// }
// }
//}
//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();
// // System.out.println(arr[i] + " ");
// }
// for(int i=0; i<n; i++) {
// System.out.println(arr[i] + " ");
// }
// for(int i=0; i<n; i++) {
// System.out.println(arr[i] + " ");
// }
//
// }
//}
//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++) {
// for(int j=i; j<n+i; j++) {
// System.out.print(arr[j%n] + " ");
// }
// System.out.println();
//
// }
//
// }
//}
//
//import java.util.*;
//
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// String str = t.nextLine();
// for(int i=0; i<str.length(); i++) {
// if(str.charAt(i)!=' ') {
// System.out.print(str.charAt(i));
// }
// }
//
// }
//}
/*
* A : 65
* Z : 91
*
* a : 97
* z L 97+25
*/
//import java.util.*;
//
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// char a = t.next().charAt(0);
//
// if(a >= 'A' && a <='Z') {
// System.out.println((char)(a + ('a'-'A')));
// }
// }
//}
//import java.util.*;
//
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// String str = t.nextLine();
// for(int i=0;i<str.length();i++) {
// if(str.charAt(i) >='A' && str.charAt(i) <='Z') {
// System.out.print((char)(str.charAt(i) + ('a'-'A')));
// }
// else if(str.charAt(i) >='a' && str.charAt(i) <='z') {
// System.out.print((char)(str.charAt(i) + ('A'-'a')));
// }
// else {
// System.out.print(str.charAt(i));
// }
// }
// }
//}
//import java.util.*;
//
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// String str = t.nextLine();
// if(str.equals("love")) {
// System.out.println("I love you.");
// }
// }
//}
//import java.util.*;
//
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// String str = t.nextLine();
// for(int i=0; i<str.length();i++) {
// System.out.print((char)(str.charAt(i) + 2));
//
// }
// System.out.println();
// for(int i=0; i<str.length();i++) {
// System.out.print((char)(((str.charAt(i)*7)%80)+48));
// }
// }
//}
//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[10000001];
//
// for(int i=0; i<a; i++) {
// int k = t.nextInt();
// arr[k] = 1;
// }
// int b = t.nextInt();
//
// for(int j=0; j<b; j++) {
// int k = t.nextInt();
// System.out.print(arr[k] +" ");
//
//
//
//
// }
// }
//}