//import java.util.*;
//class Main{
// public static void main(String[] args) {
// Scanner sc=new Scanner(System.in);
// int a=sc.nextInt();
// int b=sc.nextInt();
//
// if(b>=30)
// System.out.println(a+" "+(b-30));
// else if(b<30) {
// if(a==0)
// System.out.println(23+" "+(b+30));
// else
// System.out.println((a-1)+" "+(b+30));
// }
//
// }
//}
//import java.util.*;
//class Main{
// public static void main(String[] args) {
// Scanner sc=new Scanner(System.in);
//
// int a=sc.nextInt();
// int b=sc.nextInt();
//
// if(b%a==0)
// System.out.println(a+"*"+(b/a)+"="+b);
// else if(a%b==0)
// System.out.println(b+"*"+(a/b)+"="+a);
// else
// System.out.println("none");
// }
//}
/*
import java.util.*;
class Main{
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int year=sc.nextInt();
int month=sc.nextInt();
if(month==2) {
if(year%400==0 ||year%4==0&&year%100!=0) {
System.out.println(29);
}
else {
System.out.println(28);
}
}
else if(month==4||month==6||month==9||month==11) {
System.out.println(30);
}
else {
System.out.println(31);
}
}
}
*/
//import java.util.*;
//class Main{
// public static void main(String[] args) {
// Scanner sc=new Scanner(System.in);
//
// int a=sc.nextInt();
// int b=sc.nextInt();
//
// for(int i=a;i<=b;i++)
// if(i%2!=0)
// System.out.println(i);
// }
//}
//import java.util.*;
//class Main{
// public static void main(String[] args) {
// Scanner sc=new Scanner(System.in);
//
// int a=sc.nextInt();
// int b=sc.nextInt();
// int sum = 0;
// for(int i=a;i<=b;i++) {
// if(i%3==0)
// sum+=i;
// }
// System.out.println(sum);
// }
//}
//import java.util.*;
//class Main{
// public static void main(String[] args) {
// Scanner sc=new Scanner(System.in);
// int sum=0;
// int n=sc.nextInt();
// for(int i=0;i<n;i++) {
// int a=sc.nextInt();
// if(a%5==0)
// sum+=a;
// }
// System.out.println(sum);
// }
//}
//import java.util.*;
//class Main{
// public static void main(String[] args) {
// Scanner sc=new Scanner(System.in);
// int n=sc.nextInt();
// int k=sc.nextInt();
// int ans=1;
// for(int i=0;i<k;i++)
// ans*=n;
// System.out.println(ans);
// }
//}
//import java.util.*;
//class Main{
// public static void main(String[] args) {
// Scanner sc=new Scanner(System.in);
//
// int n=sc.nextInt();
// int a=1;
// int num=1;
// while((n/a)>=10){
// a*=10;
// num++;
// }
// System.out.println(num);
// }
//}
//import java.util.*;
//class Main{
// public static void main(String[] args) {
//
// }
//}
/*
int[] arr = new int[5];
int[][] arr = new int[10][10];
*/
//import java.util.*;
//class Main{
// public static void main(String[] args) {
// Scanner sc=new Scanner(System.in);
// String a=sc.next();
//
// for(int i=0;i<a.length();i++) {
// if(a.charAt(i)=='t')
// System.out.print(i+1+" ");
// }
// }
//}
//import java.util.*;
//class Main{
// public static void main(String[] args) {
// Scanner sc=new Scanner(System.in);
// String a=sc.nextLine();
//
// for(int i=0; i<a.length(); i++){
// if(a.charAt(i)!=' ')
// System.out.print(a.charAt(i));
//
// }
// }
//}
//import java.util.*;
//class Main{
// public static void main(String[] args) {
// Scanner sc=new Scanner(System.in);
// int n=sc.nextInt();
// int[] arr = new int[n];
// int i;
// for(i=0;i<n;i++) {
// arr[i]=sc.nextInt();
// }
// for(i=0;i<n;i++) {
// System.out.print(i+1+": ");
// for(int j=0;j<n;j++) {
// if(i!=j) {
// if(arr[i]>arr[j])
// System.out.print(">");
// else if(arr[i]<arr[j])
// System.out.print("<");
// else
// System.out.print("=");
// System.out.print(" ");
// }
//
// }
// System.out.println();
// }
// }
//}
//import java.util.*;
//class Main{
// public static void main(String[] args) {
// Scanner sc=new Scanner(System.in);
// int[][] arr=new int[10][10];
// int[] a=new int[10];
//
// for(int i=0;i<10;i++) {
// for(int j=0;j<10;j++) {
// arr[i][j] = sc.nextInt();
// }
// }
// for(int k=0;k<10;k++)
// a[k]=sc.nextInt();
//
// for(int j=0;j<10;j++) {
// if(a[j]==1) {
// System.out.print(j+1+" ");
// for(int i=9; i>=0; i--) {
//
// if(arr[i][j]>0) {
// System.out.println("crash");
// break;
// }
// else if(arr[i][j]<0) {
// System.out.println("fall");
// break;
// }
// else if(i==0){
// if(arr[0][j]==0)
// System.out.println("safe");
// }
//
// }
//
// }
// }
// }
//}
//import java.util.*;
//class Main{
// public static void main(String[] args) {
// Scanner sc=new Scanner(System.in);
// String a=sc.next();
//
// for(int i=0;i<a.length();i++) {
// if(a.charAt(i)>=65&&a.charAt(i)<97)
// System.out.printf("%c",a.charAt(i)+32);
//
// else if(a.charAt(i)>=97&&a.charAt(i)<=122)
// System.out.printf("%c",a.charAt(i)-32);
//
// else if(a.charAt(i)<58&&a.charAt(i)>47)
// System.out.printf("%c",a.charAt(i));
// else
// System.out.print(a.charAt(i));
// }
//
// }
//}
//import java.util.*;
//class Main{
// public static void main(String[] args) {
// Scanner sc=new Scanner(System.in);
//
// String a=sc.next();
// String b=sc.next();
// String c=sc.next();
//
// if(a.charAt(a.length()-1)==b.charAt(0)) {
// if(b.charAt(b.length()-1)==c.charAt(0)) {
// if(c.charAt(c.length()-1)==a.charAt(0))
// System.out.println("good");
// else
// System.out.println("bad");
// }
// else
// System.out.println("bad");
//
// }
// else
// System.out.println("bad");
//}
//}
//import java.util.*;
//class Main{
// public static void main(String[] args) {
// Scanner sc=new Scanner(System.in);
//
// String a=sc.nextLine();
//
// for(int i=0;i<a.length();i++) {
//
// if(a.charAt(i)==' ')
// System.out.print(" ");
// else {
// if(a.charAt(i)>=97&&a.charAt(i)<=99)
// System.out.print((char)(a.charAt(i)+23));
// else
// System.out.printf("%c", a.charAt(i)-3);
// }
// }
// }
//}
//100 1000
//"100000000000000000000000000000000000000004857564864867456478964565600"
//import java.util.*;
//class Main{
// public static void main(String[] args) {
// Scanner sc=new Scanner(System.in);
//
// String a=sc.next();
// int sum=0;
// for(int i=0;i<a.length();i++) {
// sum+=a.charAt(i);
// }
// if(sum%3==0)
// System.out.println(1);
// else if(sum%3!=0)
// System.out.println(0);
// }
//}
//import java.util.*;
//class Main{
// public static void main(String[] args) {
// Scanner sc=new Scanner(System.in);
// String a=sc.next();
// String b=sc.next();
// if(a.length()>b.length())
// System.out.println(b+" "+a);
// else if(b.length()>a.length())
// System.out.println(a+" "+b);
// else {
// for(int i=0;i<a.length();i++) {
// if(b.charAt(i)>a.charAt(i)) {
// System.out.println(a+" "+b);
// break;
// }
// else if(a.charAt(i)>b.charAt(i)) {
// System.out.println(b+" "+a);
// break;
// }
// }
// }
// }
//}
//import java.util.*;
//
//class Main {
// public static void main(String[] args) {
// Scanner sc = new Scanner(System.in);
// int n = sc.nextInt();
// int[] arr = new int [35];
//
// if (n > 0) {
// int i=0;
// while (n > 0) {
// arr[i]=n%2;
// i++;
// n = n / 2;
// }
// i--;
// while(i>=0) {
// System.out.print(arr[i]);
// i--;
// }
// } else if (n == 0)
// System.out.println(0);
// }
//}
//import java.util.*;
//class Main{
// public static void main(String[] args) {
// Scanner sc=new Scanner(System.in);
//
// //1. scan
// int n=sc.nextInt();
// int[][] arr=new int[n][n];
//
// for(int i=0;i<n;i++)
// arr[i][0]=sc.nextInt();
//
// //2. fill
// for(int i=1;i<n;i++) {
// for(int j=0;j<i;j++) {
// arr[i][j+1]=arr[i][j]-arr[i-1][j];
// }
// }
// //3. print
// for(int i=0;i<n;i++) {
// for(int j=0;j<=i;j++) {
// System.out.print(arr[i][j]+" ");
// }
// System.out.println();
// }
//
// }
//}
//import java.util.*;
//class Main{
// public static void main(String[] args) {
// Scanner sc=new Scanner(System.in);
//
// int h=sc.nextInt();
// int w=sc.nextInt();
// int n=sc.nextInt();
// int[][] a=new int[h+1][w+1];
//
// for(int i=0;i<n;i++) {
// int l = sc.nextInt();
// int d = sc.nextInt();
// int x = sc.nextInt();
// int y= sc.nextInt();
// for(int j=0;j<l;j++) {
// if(d==0) a[x][y+j]=1;
// else a[x+j][y]=1;
// }
// }
//
// for(int i=1;i<=h;i++) {
// for(int j=1;j<=w;j++) {
// System.out.print(a[i][j]+" ");
// }
// System.out.println();
// }
// }
//}
//import java.util.*;
//class Main{
// public static void main(String[] args) {
// Scanner sc=new Scanner(System.in);
//
// String a=sc.next();
// for(int i=0;i<a.length();i++) {
// if(a.charAt(i)!=',')
// System.out.print(a.charAt(i));
// else if(a.charAt(i)==',')
// System.out.print(" ");
// }
// System.out.println(" ");
// }
//}
//import java.util.*;
//class Main{
// public static void main(String[] args) {
// Scanner sc=new Scanner(System.in);
// int ans;
// String a=sc.next();
// if(a.length()==2)
// ans=13;
// else if(a.length()==3) {
// if(a.charAt(1)>60)
// ans=12+a.charAt(2)-48;
// else
// ans=(a.charAt(1)-48)+1-48;
// }
//
// else
// ans=(a.charAt(1)-48)*12+a.charAt(3)-48;
//
// System.out.print(ans);
// }
//}