/*
import java.util.*;
public class Main {
public static void main(String[] args) {
Vector<Integer, Integer> Nord = new Vector<Integer, Integer>();
}
}
*/
/*
import java.util.*;
public class Main {
public static void main(String[] args) {
int N, A = 1;
int arr[] = new int[10];
Scanner scan = new Scanner(System.in);
for(int i =0; i < 3; i++) {
N = scan.nextInt();
A*=N;
}
while(true) {
if(A <= 0) {
break;
}
arr[A%10]++;
A/=10;
}
for(int i = 0; i < 10; i++) {
System.out.println(arr[i]);
}
}
}
*/
/*
import java.util.*;
public class Main {
public static void main(String[] args) {
int n,c = 0;
int arr[] = new int[42];
Scanner scan = new Scanner(System.in);
for(int i = 0; i < 10; i++) {
n = scan.nextInt();
arr[n%42]++;
}
for(int i = 0; i < 42; i++) {
if(arr[i] != 0)
c++;
}
System.out.print(c);
}
}
*/
/*
import java.util.*;
public class Main {
public static void main(String[] args) {
int n,k,ave,upave;
int [] arr;
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
for(int i = 0; i < n; i++) {
k = scan.nextInt();
upave = 0; ave = 0;
arr = new int[k];
for(int j = 0; j < k; j++) {
arr[j] = scan.nextInt();
ave += arr[j];
}
ave /= k;
for(int j = 0; j < k; j++) {
if(arr[j] > ave)
upave++;
}
double s = (double)upave / k * 100;
System.out.println(String.format("%.3f", s) + '%');
}
}
}*/
/*
import java.util.*;
public class Main {
public static void main(String[] args) {
int y;
Scanner scan = new Scanner(System.in);
y = scan.nextInt();
System.out.println(y-543);
}
}
*/
/*
import java.util.*;
public class Main {
public static void main(String[] args) {
int a,b,a1,b1;
Scanner scan = new Scanner(System.in);
a = scan.nextInt();
b = scan.nextInt();
a1 = a;
b1 = b;
while(true) {
if(a1%10 > b1%10) {
while(true) {
if(a<=0) {
break;
}
System.out.print(a%10);
a/=10;
}
break;
}
if(a1%10 < b1%10) {
while(true) {
if(b<=0) {
break;
}
System.out.print(b%10);
b/=10;
}
break;
}
a1/= 10;
b1/= 10;
}
}
}
*/
/*
import java.util.*;
public class Main {
public static void main(String[] args) {
int a,b,c;
Scanner scan = new Scanner(System.in);
a = scan.nextInt();
b = scan.nextInt();
c = scan.nextInt();
System.out.println(a == b ? ( b == c ? 10000+a*1000 : 1000+a*100) : (b==c ? 1000+b*100 : (a==c ? 1000+a*100 :a > b ? (a > c ? a*100 : c*100) : (b > c ? b*100 : c*100))));
}
}
*/
/*
import java.util.*;
public class Main {
public static void main(String[] args) {
int a,b,c;
Scanner scan = new Scanner(System.in);
a = scan.nextInt();
b = scan.nextInt();
c = scan.nextInt();
System.out.println((a+((b+c)/60))%24 + " " + (b+c)%60);
}
}
*/
/*
import java.util.*;
public class Main {
public static void main(String[] args) {
int n, k = 1;
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
if(n == 0) {
System.out.println(k);
return ;
}
else {
for(int i = 1; i <= n; i++) {
k *= i;
}
System.out.println(k);
return;
}
}
}
*/
/*
import java.util.*;
public class Main {
public static void main(String[] args) {
int a,b;
Scanner scan = new Scanner(System.in);
a = scan.nextInt();
b = scan.nextInt();
System.out.println(a+b);
}
}
*/
/*
import java.util.*;
public class Main {
public static void main(String[] args) {
int a,b,c;
Scanner scan = new Scanner(System.in);
a = scan.nextInt();
b = scan.nextInt();
c = scan.nextInt();
System.out.println(b >= c ? -1 : a/(c-b) + 1);
}
}
*/
import java.util.*;
public class Main {
public static void main(String[] args) {
int A,B,V;
}
}