import java.util.*; import java.lang.*; import java.io.*; import java.awt.Point;
// SHIVAM GUPTA : //NSIT //decoder_1671 //BEING PERFECTIONIST IS NOT AN OPTION. // YOUR LOVE MAKE ME STRONGER BUT UR HATE MAKES ME STRONGEST ... NOW ITS UR CHOICE.......... // STOP NOT TILL IT IS DONE OR U DIE . //EITHER MAKE IT OR BREAK IT. //NEVER UNDERESTIMATE URSELF. // U KNOW THAT IF THIS DAY WILL BE URS THEN NO ONE CAN DEFEAT U HERE................ //MIRACLE HAPPENS .....BUT IT HAPPENS ...
// ASCII = 48 + i ;
// 2^28 = 268,435,456 > 2* 10^8
// log 10 base 2 = 3.3219
// odd:: (x^2+1)/2 , (x^2-1)/2 ; x>=3
// even:: (x^2/4)+1 ,(x^2/4)-1 x >=4
// FOR ANY ODD NO N : N,N-1,N-2 //ALL ARE PAIRWISE COPRIME //THEIR COMBINED LCM IS PRODUCT OF ALL THESE NOS
// two consecutive odds are always coprime to each other
// two consecutive even have always gcd = 2 ;
/* Name of the class has to be "Main" only if the class is public. */
public class Main {
// static int[] arr = new int[100002] ;
// static int[] dp = new int[100002] ;
static PrintWriter out;
static class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br=new BufferedReader(new InputStreamReader(System.in));
out=new PrintWriter(System.out);
}
String next(){
while(st==null || !st.hasMoreElements()){
try{
st= new StringTokenizer(br.readLine());
}
catch (IOException e){
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt(){
return Integer.parseInt(next());
}
long nextLong(){
return Long.parseLong(next());
}
double nextDouble(){
return Double.parseDouble(next());
}
String nextLine(){
String str = "";
try{
str=br.readLine();
}
catch(IOException e){
e.printStackTrace();
}
return str;
}
}//////////////////////////////////////////////////////////////////////////////////// public static int countDigit(long n) { return (int)Math.floor(Math.log10(n) + 1); }
/////////////////////////////////////////////////////////////////////////////////////////
public static int sumOfDigits(long n) {
if( n< 0)return -1 ;
int sum = 0;
while( n > 0) { sum = sum + (int)( n %10) ;
n /= 10 ;
}
return sum ;
}
//////////////////////////////////////////////////////////////////////////////////////////////////
public static long arraySum(int[] arr , int start , int end) { long ans = 0 ;
for(int i = start ; i <= end ; i++)ans += arr[i] ; return ans ;
}
/////////////////////////////////////////////////////////////////////////////////
public static int mod(int x) { if(x <0)return -1*x ; else return x ; } public static long mod(long x) { if(x <0)return -1*x ; else return x ; }
////////////////////////////////////////////////////////////////////////////////
public static void swapArray(int[] arr , int start , int end) { while(start < end) { int temp = arr[start] ; arr[start] = arr[end]; arr[end] = temp; start++ ;end-- ; } }
//////////////////////////////////////////////////////////////////////////////////
public static int[][] rotate(int[][] input){
int n =input.length; int m = input[0].length ; int[][] output = new int [m][n];
for (int i=0; i<n; i++) for (int j=0;j<m; j++) output [j][n-1-i] = input[i][j]; return output; } ///////////////////////////////////////////////////////////////////////////////////////////////////////
public static int countBits(long n) {
int count = 0; while (n != 0) { count++; n = (n) >> (1L) ; }
return count; }
/////////////////////////////////////////// ////////////////////////////////////////////////
public static boolean isPowerOfTwo(long n) { if(n==0) return false;
if(((n ) & (n-1)) == 0 ) return true ; else return false ;
}
/////////////////////////////////////////////////////////////////////////////////////
public static int min(int a ,int b , int c, int d) { int[] arr = new int[4] ; arr[0] = a;arr[1] = b ;arr[2] = c;arr[3] = d;Arrays.sort(arr) ;
return arr[0];
} ///////////////////////////////////////////////////////////////////////////// public static int max(int a ,int b , int c, int d) { int[] arr = new int[4] ; arr[0] = a;arr[1] = b ;arr[2] = c;arr[3] = d;Arrays.sort(arr) ;
return arr[3];
}
///////////////////////////////////////////////////////////////////////////////////
public static String reverse(String input) { StringBuilder str = new StringBuilder("") ;
for(int i =input.length()-1 ; i >= 0 ; i-- )
{
str.append(input.charAt(i));
}return str.toString() ; } ///////////////////////////////////////////////////////////////////////////////////////////
public static boolean sameParity(long a ,long b ) { long x = a% 2L; long y = b%2L ; if(x==y)return true ; else return false ; }
//////////////////////////////////////////////////////////////////////////////////////////////////// public static boolean isPossibleTriangle(int a ,int b , int c) { if( a + b > c && c+b > a && a +c > b)return true ; else return false ; }
//////////////////////////////////////////////////////////////////////////////////////////// static long xnor(long num1, long num2) { if (num1 < num2) { long temp = num1; num1 = num2; num2 = temp; } num1 = togglebit(num1); return num1 ^ num2; }
static long togglebit(long n) {
if (n == 0)
return 1;
long i = n;
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
return i ^ n;
}
///////////////////////////////////////////////////////////////////////////////////////////////
public static int xorOfFirstN(int n) {
if( n % 4 ==0)return n ;
else if( n % 4 == 1)return 1 ;
else if( n % 4 == 2)return n+1 ;
else return 0 ;
} //////////////////////////////////////////////////////////////////////////////////////////////
public static int gcd(int a, int b ) {
if(b==0)return a ;
else return gcd(b,a%b) ;
}
public static long gcd(long a, long b ) {
if(b==0)return a ;
else return gcd(b,a%b) ;
}
////////////////////////////////////////////////////////////////////////////////////
public static int lcm(int a, int b ,int c , int d ) {
int temp = lcm(a,b , c) ;
int ans = lcm(temp ,d ) ;
return ans ;
}
///////////////////////////////////////////////////////////////////////////////////////////
public static int lcm(int a, int b ,int c ) {
int temp = lcm(a,b) ;
int ans = lcm(temp ,c) ;
return ans ;
}
////////////////////////////////////////////////////////////////////////////////////////
public static int lcm(int a , int b ) {
int gc = gcd(a,b);
return (a*b)/gc ; }
public static long lcm(long a , long b ) {
long gc = gcd(a,b);
return (a*b)/gc ; }
/////////////////////////////////////////////////////////////////////////////////////////// static boolean isPrime(long n) { if(n==1) { return false ; }
boolean ans = true ;
for(long i = 2L; i*i <= n ;i++)
{
if(n% i ==0)
{
ans = false ;break ;
}
}
return ans ;}
///////////////////////////////////////////////////////////////////////////
static int sieve = 1000000 ;
static boolean[] prime = new boolean[sieve + 1] ;
public static void sieveOfEratosthenes() { // FALSE == prime
// TRUE == COMPOSITE
// FALSE== 1
// time complexity = 0(NlogLogN)== o(N)
// gives prime nos bw 1 to N
for(int i = 4; i<= sieve ; i++)
{
prime[i] = true ;
i++ ;
}
for(int p = 3; p*p <= sieve; p++)
{
if(prime[p] == false)
{
for(int i = p*p; i <= sieve; i += p)
prime[i] = true;
}
p++ ;
}
}///////////////////////////////////////////////////////////////////////////////////
public static void sortD(int[] arr , int s , int e) { sort(arr ,s , e) ;
int i =s ; int j = e ;
while( i < j)
{
int temp = arr[i] ;
arr[i] =arr[j] ;
arr[j] = temp ;
i++ ; j-- ;
}
return ;}
/////////////////////////////////////////////////////////////////////////////////////////
public static long countSubarraysSumToK(long[] arr ,long sum ) { HashMap<Long,Long> map = new HashMap<>() ;
int n = arr.length ;
long prefixsum = 0 ;
long count = 0L ;
for(int i = 0; i < n ; i++)
{
prefixsum = prefixsum + arr[i] ;
if(sum == prefixsum)count = count+1 ;
if(map.containsKey(prefixsum -sum))
{
count = count + map.get(prefixsum -sum) ;
}
if(map.containsKey(prefixsum ))
{
map.put(prefixsum , map.get(prefixsum) +1 );
}
else{
map.put(prefixsum , 1L );
}
}
return count ;
}///////////////////////////////////////////////////////////////////////////////////////////////
// KMP ALGORITHM : TIME COMPL:O(N+M) // FINDS THE OCCURENCES OF PATTERN AS A SUBSTRING IN STRING //RETURN THE ARRAYLIST OF INDEXES // IF SIZE OF LIST IS ZERO MEANS PATTERN IS NOT PRESENT IN STRING
public static ArrayList kmpAlgorithm(String str , String pat) { ArrayList list =new ArrayList<>();
int n = str.length() ;
int m = pat.length() ;
String q = pat + "#" + str ;
int[] lps =new int[n+m+1] ;
longestPefixSuffix(lps, q,(n+m+1)) ;
for(int i =m+1 ; i < (n+m+1) ; i++ )
{
if(lps[i] == m)
{
list.add(i-2*m) ;
}
}
return list ;
}public static void longestPefixSuffix(int[] lps ,String str , int n) { lps[0] = 0 ;
for(int i = 1 ; i<= n-1; i++)
{
int l = lps[i-1] ;
while( l > 0 && str.charAt(i) != str.charAt(l))
{
l = lps[l-1] ;
}
if(str.charAt(i) == str.charAt(l))
{
l++ ;
}
lps[i] = l ;
}
}/////////////////////////////////////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////////////////////////////////////////
// CALCULATE TOTIENT Fn FOR ALL VALUES FROM 1 TO n // TOTIENT(N) = count of nos less than n and grater than 1 whose gcd with n is 1 // or n and the no will be coprime in nature //time : O(n*(log(logn)))
public static void eulerTotientFunction(int[] arr ,int n )
{
for(int i = 1; i <= n ;i++)arr[i] =i ;
for(int i= 2 ; i<= n ;i++)
{
if(arr[i] == i)
{
arr[i] =i-1 ;
for(int j =2*i ; j<= n ; j+= i )
{
arr[j] = (arr[j]*(i-1))/i ;
}
}
}
return ;
}///////////////////////////////////////////////////////////////////////////////////////////// public static long nCr(int n,int k) { long ans=1L; k=k>n-k?n-k:k; int j=1; for(;j<=k;j++,n--) { if(n%j==0) { ans*=n/j; }else if(ans%j==0) { ans=ans/j*n; }else { ans=(ans*n)/j; } } return ans; }
///////////////////////////////////////////////////////////////////////////////////////////
public static ArrayList allFactors(int n) {
ArrayList list = new ArrayList<>() ;
for(int i = 1; i*i <= n ;i++)
{
if( n % i == 0)
{
if(i*i == n)
{
list.add(i) ;
}
else{
list.add(i) ;
list.add(n/i) ;
}
}
}
return list ;}
public static ArrayList allFactors(long n) {
ArrayList list = new ArrayList<>() ;
for(long i = 1L; i*i <= n ;i++)
{
if( n % i == 0)
{
if(i*i == n)
{
list.add(i) ;
}
else{
list.add(i) ;
list.add(n/i) ;
}
}
}
return list ;} ////////////////////////////////////////////////////////////////////////////////////////////////////
static final int MAXN = 10000001;
static int spf[] = new int[MAXN];
static void sieve()
{
spf[1] = 1;
for (int i=2; i<MAXN; i++)
spf[i] = i;
for (int i=4; i<MAXN; i+=2)
spf[i] = 2;
for (int i=3; i*i<MAXN; i++)
{
if (spf[i] == i)
{
for (int j=i*i; j<MAXN; j+=i)
if (spf[j]==j)
spf[j] = i;
}
}
}// The above code works well for n upto the order of 10^7. // Beyond this we will face memory issues.
// Time Complexity: The precomputation for smallest prime factor is done in O(n log log n) // using sieve. // Where as in the calculation step we are dividing the number every time by // the smallest prime number till it becomes 1. // So, let’s consider a worst case in which every time the SPF is 2 . // Therefore will have log n division steps.
// Hence, We can say that our Time Complexity will be O(log n) in worst case.
static Vector<Integer> getFactorization(int x)
{
Vector<Integer> ret = new Vector<>();
while (x != 1)
{
ret.add(spf[x]);
x = x / spf[x];
}
return ret;
}////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////
public static void merge(int arr[], int l, int m, int r) { // Find sizes of two subarrays to be merged int n1 = m — l + 1; int n2 = r — m;
/* Create temp arrays */
int L[] = new int[n1];
int R[] = new int[n2];
/*Copy data to temp arrays*/
for (int i=0; i<n1; ++i)
L[i] = arr[l + i];
for (int j=0; j<n2; ++j)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarry array
int k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy remaining elements of R[] if any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
// Main function that sorts arr[l..r] using
// merge()public static void sort(int arr[], int l, int r) { if (l < r) { // Find the middle point int m = (l+r)/2;
// Sort first and second halves
sort(arr, l, m);
sort(arr , m+1, r);
// Merge the sorted halves
merge(arr, l, m, r);
}
}public static void sort(long arr[], int l, int r) { if (l < r) { // Find the middle point int m = (l+r)/2;
// Sort first and second halves
sort(arr, l, m);
sort(arr , m+1, r);
// Merge the sorted halves
merge(arr, l, m, r);
}
}public static void merge(long arr[], int l, int m, int r) { // Find sizes of two subarrays to be merged int n1 = m — l + 1; int n2 = r — m;
/* Create temp arrays */
long L[] = new long[n1];
long R[] = new long[n2];
/*Copy data to temp arrays*/
for (int i=0; i<n1; ++i)
L[i] = arr[l + i];
for (int j=0; j<n2; ++j)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarry array
int k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy remaining elements of R[] if any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}/////////////////////////////////////////////////////////////////////////////////////////
public static long knapsack(int[] weight,long value[],int maxWeight){
int n= value.length ;
//dp[i] stores the profit with KnapSack capacity "i"
long []dp = new long[maxWeight+1];
//initially profit with 0 to W KnapSack capacity is 0
Arrays.fill(dp, 0);
// iterate through all items
for(int i=0; i < n; i++)
//traverse dp array from right to left
for(int j = maxWeight; j >= weight[i]; j--)
dp[j] = Math.max(dp[j] , value[i] + dp[j - weight[i]]);
/*above line finds out maximum of dp[j](excluding ith element value)
and val[i] + dp[j-wt[i]] (including ith element value and the
profit with "KnapSack capacity - ith element weight") */
return dp[maxWeight];
}/////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////
// to return max sum of any subarray in given array public static long kadanesAlgorithm(long[] arr) { long[] dp = new long[arr.length] ;
dp[0] = arr[0] ;
long max = dp[0] ;
for(int i = 1; i < arr.length ; i++)
{
if(dp[i-1] > 0)
{
dp[i] = dp[i-1] + arr[i] ;
}
else{
dp[i] = arr[i] ;
}
if(dp[i] > max)max = dp[i] ;
}
return max ;} ///////////////////////////////////////////////////////////////////////////////////////////// public static long kadanesAlgorithm(int[] arr) { long[] dp = new long[arr.length] ;
dp[0] = arr[0] ;
long max = dp[0] ;
for(int i = 1; i < arr.length ; i++)
{
if(dp[i-1] > 0)
{
dp[i] = dp[i-1] + arr[i] ;
}
else{
dp[i] = arr[i] ;
}
if(dp[i] > max)max = dp[i] ;
}
return max ;}
///////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////
public static long binarySerachGreater(int[] arr , int start , int end , int val) {
// fing total no of elements strictly grater than val in sorted array arr
if(start > end)return 0 ; //Base case
int mid = (start + end)/2 ;
if(arr[mid] <=val)
{
return binarySerachGreater(arr,mid+1, end ,val) ;
}
else{
return binarySerachGreater(arr,start , mid -1,val) + end-mid+1 ;
}}
////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////////
//TO GENERATE ALL(DUPLICATE ALSO EXIST) PERMUTATIONS OF A STRING
// JUST CALL generatePermutation( str, start, end) start :inclusive ,end : exclusive
//Function for swapping the characters at position I with character at position j
public static String swapString(String a, int i, int j) {
char[] b =a.toCharArray();
char ch;
ch = b[i];
b[i] = b[j];
b[j] = ch;
return String.valueOf(b);
}
//Function for generating different permutations of the string
public static void generatePermutation(String str, int start, int end)
{
//Prints the permutations
if (start == end-1)
System.out.println(str);
else
{
for (int i = start; i < end; i++)
{
//Swapping the string by fixing a character
str = swapString(str,start,i);
//Recursively calling function generatePermutation() for rest of the characters
generatePermutation(str,start+1,end);
//Backtracking and swapping the characters again.
str = swapString(str,start,i);
}
}
}
//////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////
public static long factMod(long n, long mod) { if (n <= 1) return 1; long ans = 1; for (int i = 1; i <= n; i++) { ans = (ans * i) % mod; } return ans; }
///////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////
public static long power(int x ,int n) { //time comp : o(logn)
if(n==0)return 1 ;
if(n==1)return x;
long ans =1L ;
while(n>0)
{
if(n % 2 ==1)
{
ans = ans *x ;
}
n /= 2 ;
x = x*x ;
}
return ans ;
}//////////////////////////////////////////////////////////////////////////////////////////////////// public static long powerMod(long x, long n, long mod) { //time comp : o(logn)
if(n==0)return 1L ;
if(n==1)return x;
long ans = 1;
while (n > 0) {
if (n % 2 == 1) ans = (ans * x) % mod;
x = (x * x) % mod;
n /= 2;
}
return ans;}
//////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////
/* lowerBound — finds largest element equal or less than value paased upperBound — finds smallest element equal or more than value passed
if not present return -1;
*/
public static long lowerBound(long[] arr,long k) { long ans=-1;
int start=0;
int end=arr.length-1;
while(start<=end)
{
int mid=(start+end)/2;
if(arr[mid]<=k)
{
ans=arr[mid];
start=mid+1;
}
else
{
end=mid-1;
}
}
return ans;
}
public static int lowerBound(int[] arr,int k)
{
int ans=-1;
int start=0;
int end=arr.length-1;
while(start<=end)
{
int mid=(start+end)/2;
if(arr[mid]<=k)
{
ans=arr[mid];
start=mid+1;
}
else
{
end=mid-1;
}
}
return ans;
}
public static long upperBound(long[] arr,long k)
{
long ans=-1;
int start=0;
int end=arr.length-1;
while(start<=end)
{
int mid=(start+end)/2;
if(arr[mid]>=k)
{
ans=arr[mid];
end=mid-1;
}
else
{
start=mid+1;
}
}
return ans;
}
public static int upperBound(int[] arr,int k)
{
int ans=-1;
int start=0;
int end=arr.length-1;
while(start<=end)
{
int mid=(start+end)/2;
if(arr[mid]>=k)
{
ans=arr[mid];
end=mid-1;
}
else
{
start=mid+1;
}
}
return ans;
}
//////////////////////////////////////////////////////////////////////////////////////////
public static void printArray(int[] arr , int si ,int ei) { for(int i = si ; i <= ei ; i++) { out.print(arr[i] +" ") ; }
}
public static void printArrayln(int[] arr , int si ,int ei) { for(int i = si ; i <= ei ; i++) { out.print(arr[i] +" ") ; } out.println() ; }
public static void printLArray(long[] arr , int si , int ei) { for(int i = si ; i <= ei ; i++) { out.print(arr[i] +" ") ; }
}
public static void printLArrayln(long[] arr , int si , int ei) { for(int i = si ; i <= ei ; i++) { out.print(arr[i] +" ") ; } out.println() ;
}
///////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////////////////
static ArrayList[] tree ; static long[] child; static int mod= 1000000007 ; static int[][] pre = new int[3001][3001]; static int[][] suf = new int[3001][3001] ;
//program to calculate noof nodes in subtree for every vertex including itself
// static void dfs(int sv) // { // child[sv] = 1L;
// for(Integer x : tree[sv]) // { // if(child[x] == 0) // {
// dfs(x) ;
// child[sv] += child[x] ; // } // } // }
////////////////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////////////////
public static void solve() { FastReader scn = new FastReader() ;
//int[] store = {2 ,3, 5 , 7 ,11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 } ;
// product of first 11 prime nos is greater than 10 ^ 12;
//ArrayList arr[] = new ArrayList[n] ; ArrayList list = new ArrayList<>() ; ArrayList listl = new ArrayList<>() ; //ArrayList lista = new ArrayList<>() ; //ArrayList listb = new ArrayList<>() ; //ArrayList lists = new ArrayList<>() ;
HashMap<Integer,Integer> map = new HashMap<>() ; //HashMap<Long,Long> map = new HashMap<>() ; HashMap<Integer,Integer> map1 = new HashMap<>() ; HashMap<Integer,Integer> map2 = new HashMap<>() ; //HashMap<String,Integer> maps = new HashMap<>() ; //HashMap<Integer,Boolean> mapb = new HashMap<>() ; //HashMap<Point,Integer> point = new HashMap<>() ;
Set set = new HashSet<>() ; Set setx = new HashSet<>() ; Set sety = new HashSet<>() ;
StringBuilder sb =new StringBuilder("") ;
//Collections.sort(list);
//if(map.containsKey(arr[i]))map.put(arr[i] , map.get(arr[i]) +1 ) ; //else map.put(arr[i],1) ;
// if(map.containsKey(temp))map.put(temp , map.get(temp) +1 ) ; // else map.put(temp,1) ;
//int bit =Integer.bitCount(n); // gives total no of set bits in n;
// Arrays.sort(arr, new Comparator() { // @Override // public int compare(Pair a, Pair b) { // if (a.first != b.first) { // return a.first — b.first; // for increasing order of first // } // return a.second — b.second ; //if first is same then sort on second basis // } // });
int testcase = 1;
// testcase = scn.nextInt() ;
while(testcase-- > 0) {
//if(map.containsKey(arr[i]))map.put(arr[i],map.get(arr[i])+1) ;else map.put(arr[i],1) ; //if(map.containsKey(temp))map.put(temp,map.get(temp)+1) ;else map.put(temp,1) ;
// tree = new ArrayList[n] ;
// child = new long[n] ;
// for(int i = 0; i< n; i++) // { // tree[i] = new ArrayList(); // }
//int n = scn.nextInt() ; //int m = scn.nextInt() ; //int k = scn.nextInt() ;
// long n = scn.nextLong() ; //long a = scn.nextLong() ; //int[] arr = new int[n+1] ; //for(int i = 0 ; i < arr.length ; i++){ //Arrays.fill(arr,-1) ; //long b = scn.nextLong() ; //long[] arr = new long[n] ; for(int i = 0 ; i < n ;i++)arr[i] = scn.nextLong() ;
long a = scn.nextLong() ;long b = scn.nextLong() ;long x = scn.nextLong() ;long y = scn.nextLong() ;
//int a = scn.nextInt() ;int b = scn.nextInt() ;int x = scn.nextInt() ;int y = scn.nextInt() ;
if((a < x) || (b < y)) { out.println(0 +" " + 0) ; }
else{
long tempx = x; long tempy = y ;
while( a >= tempx && b >= tempy)
{
tempx = tempx +x ; tempy = tempy + y ;
}
out.println((tempx-x)+" " + (tempy-y)) ;// out.println((tempx)+" " + (tempy)) ;
}
//out.println() ;
//out.println(ans) ;
//out.println(ans) ;
//out.println() ;
//for(int i = 0; i < n; i++)out.print(arr[i]+ " ") ;
// for(int i = 0; i < arr.length ; i++) // { // for(int j = 0; j < arr[0].length ; j ++) // { // out.print(arr[i][j] +" "); // } // out.println() ; // }
sb.delete(0 , sb.length()) ; list.clear() ; map.clear() ; map1.clear() ; map2.clear() ; set.clear() ;
} // test case end loop
out.flush() ;
} // solve fn ends
public static void main (String[] args) throws java.lang.Exception {
solve() ;
}
}
class Pair { int first ;
int second ;
@Override public String toString() {
String ans = "" ;
ans += this.first ;
ans += " ";
ans += this.second ;
return ans ;
}
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// PROBLEM LINK :-https://codeforces.net/contest/16/problem/C I KNOW MY LOGIC IS NOT CORRECT BUT THEN IT SHOULD GIVE WRONG ANSWER NOT RUNTIME ERROR. PLZ ANY JAVA GEEK HELP ....
