//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++)
// {
// if(b[i] == ' ')
// {
// continue;
// }
// else
// {
// 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();
// char[] c = str.toCharArray();
//
// for(int i=0; i<b.length; i++)
// {
// b[i]+=2;
// c[i]*=7;
// c[i]%=80;
// c[i]+=48;
// }
//
// System.out.println(b);
// System.out.println(c);
// }
//}
//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();
// int a=0;
// int c=0;
//
// for(int i=0; i<b.length; i++)
// {
// if(b[i] == '(')
// {
// a++;
// }
// else if(b[i] == ')')
// {
// c++;
// }
// }
// System.out.printf("%d %d", a, c);
// }
//}
//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();
// int a = 0;
// int c = 0;
//
// for(int i=0; i<b.length; i++)
// {
// if(b[i]=='c' || b[i] == 'C')
// {
// a++;
// if(b[i+1] == 'c'|| b[i+1] == 'C' )
// {
// c++;
// }
// }
// }
// System.out.printf("%d\n%d", a,c);
// }
//}
//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++)
// {
// if(b[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.nextLine();
// char[] b = str.toCharArray();
// int a=0;
//
// for(int i=0; i<b.length; i++)
// {
// if(b[i] == 'l' && b[i+1] == 'o' && b[i+2] == 'v' && b[i+3] == 'e')
// {
// a++;
// }
// }
// System.out.println(a);
// }
//}
//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("IOI"))
// {
// System.out.printf("IOI is the International Olympiad in Informatics.");
// }
// else
// {
// System.out.printf("I don't care.");
// }
//
// }
//}
//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();
//
// if(a.length()<b.length())System.out.println(a+" "+b);
// else if (a.length() == b.length()) {
// if(a.compareTo(b)> 0 )System.out.println(b+" "+a);
// else System.out.println(a+" "+b);
// }else System.out.println(b+" "+a);
// }
//}
//import java.util.*;
//public class Main
//{
// public static void main(String[] args)
// {
// Scanner t = new Scanner(System.in);
// String str = t.next();
// int sum=0;
//
// for(int i=0; i<str.length(); i++)
// {
// sum+=str.charAt(i)-'0';
// }
// System.out.println(sum);
//
// if(sum%3 == 0)
// {
// System.out.printf("1");
// }
// else
// {
// System.out.printf("0");
// }
// }
//}
//import java.util.*;
//public class Main
//{
// public static void main(String[] args)
// {
// Scanner t = new Scanner(System.in);
// String s1 = t.next();
// String s2 = t.next();
// String s3 = t.next();
//
// int s11 = s1.length()-1;
// int s22 = s2.length()-1;
// int s33 = s3.length()-1;
// if(s1.charAt(s11) == s2.charAt(0) && s2.charAt(s22) == s3.charAt(0) && s3.charAt(s33) == s1.charAt(0))
// {
// System.out.println("good");
// return;
// }
// else
// {
// System.out.println("bad");
// return;
// }
// }
//}
//import java.util.*;
//public class Main
//{
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
// String str = t.next();
// System.out.printf("welcome! %s", str);
// }
//}
//1508 1509 1513 1525 1507 1505
//import java.util.*;
//public class Main
//{
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
// int[][] a = new int[100][100];
// int n = t.nextInt();
// for(int i=0; i<n; i++)
// {
// a[i][0] = t.nextInt();
// }
//
//
//
// for(int i=0; i<n; i++)
// {
// for(int j=0; j<=i; j++)
// {
// a[i+1][j+1] = a[i+1][j] - a[i][j];
// }
// }
//
// for(int i=0; i<n; i++)
// {
// for(int j=0; j<=i; j++)
// {
// System.out.print(a[i][j]+ " ");
// }
// System.out.println();
// }
// }
//}
//import java.util.*;
//public class Main
//{
// public static void main(String[] args)
// {
// Scanner t = new Scanner(System.in);
// int[][] board = new int[11][10];
//
// for(int i=0; i<11; i++)
// {
// for(int j=0; j<10; j++)
// {
// board[i][j] = t.nextInt();
// }
// }
//
// for(int i=0; i<10; i++)
// {
// if(board[10][i] == 1)
// {
// System.out.printf("%d ", i+1);
// for(int j=9; j>=0; j--)
// {
// if(board[j][i] > 0)
// {
// System.out.println("crash");
// break;
// }
// else if(board[j][i]<0)
// {
// System.out.println("fall");
// break;
// }
// else if(j==0)
// {
// System.out.println("safe");
// break;
// }
// }
// }
// }
// }
//}