Reca company makes monitors, the most popular of their models is AB999 with the screen size a × b centimeters. Because of some production peculiarities a screen parameters are integer numbers. Recently the screen sides ratio x: y became popular with users. That's why the company wants to reduce monitor AB999 size so that its screen sides ratio becomes x: y, at the same time they want its total area to be maximal of all possible variants. Your task is to find the screen parameters of the reduced size model, or find out that such a reduction can't be performed.

Input

The first line of the input contains 4 integers — a, b, x and y (1 ≤ a, b, x, y ≤ 2·109).

Output

If the answer exists, output 2 positive integers — screen parameters of the reduced size model. Output 0 0 otherwise.

Examples

Input

800 600 4 3


Output

800 600


Input

1920 1200 16 9


Output

1920 1080


Input

1 1 1 2


Output

0 0

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Number theory

Sorting


Solutions:
import os
import sys
from math import *
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz'
M = 10 ** 9 + 7
EPS = 1e-06

def Ceil(a, b):
	return a // b + int(a % b > 0)

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
(a, b, x, y) = value()
gc = gcd(x, y)
x //= gc
y //= gc
l = a // x
l = min(l, b // y)
print(l * x, l * y)


import sys
from collections import defaultdict as dd
from collections import deque

def eprint(*args):
	print(*args, file=sys.stderr)
pl = 1
from math import *
import copy
if pl:
	input = sys.stdin.readline

def li():
	return [int(xxx) for xxx in input().split()]

def fi():
	return int(input())

def si():
	return list(input().rstrip())

def mi():
	return map(int, input().split())
d = []
from bisect import *
from itertools import permutations
from bisect import *
f = [0 for i in range(100)]
for i in range(1, 100):
	if i == 1:
		f[i] = 1
	else:
		f[i] = 2 * f[i - 1] + 1

def rec(n, k):
	s = []
	while n != 0:
		(n, r) = (n // k, n % k)
		if r < 0:
			r -= k
			n += 1
		s.append(r)
	return s
(a, b, x, y) = mi()
g = gcd(x, y)
x //= g
y //= g
l = 1
r = 10 ** 10
ans = 0
aa = [0, 0]
while l <= r:
	mid = (l + r) // 2
	if x * mid <= a and y * mid <= b:
		ans = max(ans, x * y * mid ** 2)
		aa = [x * mid, y * mid]
		l = mid + 1
	else:
		r = mid - 1
print(*aa)


def gcd(a, b):
	if a % b == 0:
		return b
	return gcd(b, a % b)
(a, b, x, y) = map(int, input().split())
t = gcd(x, y)
(x, y) = (x // t, y // t)
k = min(a // x, b // y)
print(k * x, k * y)


def dt(a, b):
	while b != 0:
		(a, b) = (b, a % b)
	return a
(a1, b1, x, y) = map(int, input().split())
t = dt(x, y)
x1 = x // t
y1 = y // t
d = min(a1 // x1, b1 // y1)
print('{} {}'.format(d * x1, d * y1))


from fractions import gcd
(a, b, x, y) = map(int, input().split())
m = gcd(x, y)
(x, y) = (x // m, y // m)
m = min(a // x, b // y)
print(x * m, y * m)


import sys
import math
import bisect

def solve(a, b, x, y):
	t1 = a // x
	t2 = b // y
	t = min(t1, t2)
	return (t * x, t * y)

def main():
	(a, b, x, y) = map(int, input().split())
	g = math.gcd(x, y)
	x //= g
	y //= g
	ans = solve(a, b, x, y)
	print('%d %d' % (ans[0], ans[1]))
main()


f = lambda x, y: f(y % x, x) if x else y
(a, b, x, y) = map(int, input().split())
z = f(x, y)
x //= z
y //= z
m = min(a // x, b // y)
print(m * x, m * y)


def GCD(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
(n, m, x, y) = map(int, input().split())
q = GCD(x, y)
x = x // q
y = y // q
n1 = n // x
n11 = n1 * x
m1 = n1 * y
m2 = m // y
m21 = m2 * y
n2 = m2 * x
c1 = n11 * m1
c2 = m21 * n2
c = n * m
if c >= c1 and c >= c2:
	if c1 >= c2:
		print(n11, m1)
	else:
		print(n2, m21)
elif c >= c1 and c < c2:
	print(n11, m1)
elif c < c1 and c >= c2:
	print(n2, m21)
else:
	print(0, 0)


import math
(p, q, r, s) = [int(i) for i in input().split()]
g = math.gcd(r, s)
r //= g
s //= g
e = min(p // r, q // s)
print(e * r, e * s)


def gcd(a, b):
	return a if b == 0 else gcd(b, a % b)
(a, b, x, y) = map(int, input().split())
g = gcd(x, y)
(x, y) = (x // g, y // g)
lo = 0
hi = 2000000000
while lo != hi:
	mid = (lo + hi + 1) // 2
	if mid * x <= a and mid * y <= b:
		lo = mid
	else:
		hi = mid - 1
print(lo * x, lo * y)


import sys
from array import array
from math import gcd

def input():
	return sys.stdin.buffer.readline().decode('utf-8')
(a, b, x, y) = map(int, input().split())
(x, y) = (x // gcd(x, y), y // gcd(x, y))
(ok, ng) = (0, a + 1)
while abs(ok - ng) > 1:
	mid = ok + ng >> 1
	if mid * x <= a and mid * y <= b:
		ok = mid
	else:
		ng = mid
print(ok * x, ok * y)


from fractions import gcd
(a, b, x, y) = map(int, input().split())
g = gcd(x, y)
(x, y) = (x // g, y // g)
v = min(a // x, b // y)
print(v * x, v * y)


(a, b, x, y) = map(int, input().split())
from math import gcd
g = gcd(x, y)
x //= g
y //= g
res = min(a // x, b // y)
print(x * res, y * res)


from fractions import gcd

class Monitor:

	@staticmethod
	def read_input():
		a_b_x_y = list(map(int, input('').split()))
		return (a_b_x_y[0], a_b_x_y[1], a_b_x_y[2], a_b_x_y[3])

	@staticmethod
	def compute_ratio(a, b, x, y):
		g = gcd(x, y)
		(x, y) = (x / g, y / g)
		m = min(a // x, b // y)
		(a, b) = (int(x * m), int(y * m))
		print(a, b)

	@staticmethod
	def run():
		(a, b, x, y) = Monitor.read_input()
		if a <= 1 and b <= 1:
			print(0, 0)
		elif float(a / b) == float(x / y):
			print(a, b)
		else:
			Monitor.compute_ratio(a, b, x, y)
Monitor.run()


from fractions import gcd
(a, b, x, y) = map(int, input().split())
z = gcd(x, y)
x //= z
y //= z
c = min(a // x, b // y)
print(c * x, c * y)


import math
(a, b, c, d) = [int(i) for i in input().split()]
g = math.gcd(c, d)
c //= g
d //= g
e = min(a // c, b // d)
print(e * c, e * d)


def gcd(a, b):
	return gcd(b % a, a) if a else b
(a, b, x, y) = map(int, input().split())
d = gcd(x, y)
(x, y) = (x // d, y // d)
k = min(a // x, b // y)
print(k * x, k * y)


__author__ = 'Darren'

def solve():
	(a, b, x, y) = map(int, input().split())
	g = gcd(x, y)
	(x, y) = (x // g, y // g)
	(ans, the_a, the_b) = (0, 0, 0)
	(na, nb) = (a // x * x, a // x * y)
	if nb > b:
		nb = 0
	if na * nb > ans:
		(ans, the_a, the_b) = (na * nb, na, nb)
	(nb, na) = (b // y * y, b // y * x)
	if na > a:
		na = 0
	if na * nb > ans:
		(ans, the_a, the_b) = (na * nb, na, nb)
	if ans == 0:
		print(0, 0)
	else:
		print(the_a, the_b)

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
solve()


from math import gcd
var = list(map(int, input().split()))
mcd = gcd(var[2], var[3])
div = min(var[0] // (var[2] // mcd), var[1] // (var[3] // mcd))
print(str(var[2] // mcd * div) + ' ' + str(var[3] // mcd * div))


def greatest_common_divisor(m, n):
	while n != 0:
		(m, n) = (n, m % n)
	return m

def reca(a, b, x, y):
	gcd = greatest_common_divisor(x, y)
	x //= gcd
	y //= gcd
	if a < x or b < y:
		print(0, 0)
		return
	min_a = a // x
	min_b = b // y
	max_factor = min(min_a, min_b)
	a = max_factor * x
	b = max_factor * y
	print(a, b)
(a, b, x, y) = map(int, input().split())
reca(a, b, x, y)


def mi():
	return map(int, input().split())
(a, b, x, y) = mi()
from math import gcd
t = gcd(x, y)
x //= t
y //= t
t = min(a // x, b // y)
print(t * x, t * y)


from math import gcd
(a, b, c, d) = map(int, input().split())
g = gcd(c, d)
(c, d) = (c // g, d // g)
t = min(a // c, b // d)
print(c * t, d * t)


import sys, os, io
from sys import stdin
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import math
alphabets = list('abcdefghijklmnopqrstuvwxyz')

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def si():
	return input()

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():
	(a, b, x, y) = li()
	l = 1
	g = gcd(x, y)
	x //= g
	y //= g
	k = min(b // y, a // x)
	print(k * x, k * y)
t = 1
for _ in range(t):
	solve()


import sys
import math
input = sys.stdin.readline

def inp():
	return int(input())

def inara():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
(a, b, x, y) = invr()
g = math.gcd(x, y)
x //= g
y //= g
hi = int(3000000000.0)
lo = 0
ans = 0
while hi >= lo:
	mid = (hi + lo) // 2
	if mid * x <= a and mid * y <= b:
		ans = mid
		lo = mid + 1
	else:
		hi = mid - 1
print(x * ans, y * ans)


import sys
import math
input = sys.stdin.readline
mod = 10 ** 9 + 7

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
(a, b, x, y) = invr()
h = math.gcd(x, y)
x = x / h
y = y / h
if x > a or y > b:
	print('0 0')
else:
	m = []
	f = min(a // x, b // y)
	m.append([x * f, y * f])
	f = min(b // x, a // y)
	m.append([f * x, y * f])
	print(' '.join((str(int(i)) for i in m[0])))


def gcd(i, j):
	if i == 0:
		return j
	else:
		return gcd(j % i, i)
(a, b, c, d) = map(int, input().split())
n = gcd(c, d)
(c, d) = (c // n, d // n)
k = min(a // c, b // d)
print(c * k, d * k)


import math
(a, b, x, y) = map(int, input().split(' '))
gcdd = math.gcd(x, y)
x /= gcdd
y /= gcdd
aux = int(a / x)
aux2 = int(b / y)
menor = min(aux, aux2)
print(int(x * menor), '', int(y * menor))


from math import gcd
(a, b, x, y) = list(map(int, input().split()))
g = gcd(x, y)
x //= g
y //= g
k = min(a // x, b // y)
print(k * x, k * y)


def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
(a, b, x, y) = input().split()
a = int(a)
b = int(b)
x = int(x)
y = int(y)
pig = gcd(x, y)
x //= pig
y //= pig
lav = min(a // x, b // y)
print(lav * x, lav * y)


def gcd(a, b):
	return a if b == 0 else gcd(b, a % b)

def main():
	(width, height, x, y) = map(int, input().split())
	g = gcd(x, y)
	(x, y) = (x // g, y // g)
	mx_factor_width = width // x
	mx_factor_height = height // y
	common_factor = min(mx_factor_height, mx_factor_width)
	print('{} {}'.format(x * common_factor, y * common_factor))
main()


from math import *
(a, b, x, y) = list(map(int, input().split()))
c = gcd(x, y)
x //= c
y //= c
if a < x or b < y:
	print(0, 0)
else:
	d = min(a // x, b // y)
	print(d * x, d * y)


(a, b, x, y) = [int(x) for x in input().split()]

def gcd(r, s):
	if r == 0 or s == 0:
		return r + s
	elif r > s:
		return gcd(r % s, s)
	else:
		return gcd(r, s % r)
g = gcd(x, y)
x1 = int(x / g)
y1 = int(y / g)
if x1 <= a and y1 <= b:
	c = 0
	while x1 * c <= a and y1 * c <= b:
		c += 1
	print(x1 * (c - 1), y1 * (c - 1))
else:
	print(0, 0)


from math import gcd
(a, b, x, y) = map(int, input().split())
t1 = gcd(x, y)
x /= t1
y /= t1
(x, y) = (int(x), int(y))
if a >= x and b >= y:
	(ch1, ch2) = (a // x * x, a // x * y)
	c = 0
	while ch1 > a:
		ch1 //= 2
		ch2 //= 2
		c += 1
	while ch2 > b:
		ch1 //= 2
		ch2 //= 2
		c += 1
	c -= min(c, 2)
	tt1 = 2 ** c
	while x * tt1 <= a and y * tt1 <= b:
		tt1 += 1
	tt1 -= 1
	if x * tt1 > a or y * tt1 > b:
		print(x, y)
	else:
		print(x * tt1, y * tt1)
else:
	print(0, 0)


import math
(a, b, x, y) = map(int, input().split())
e = math.gcd(x, y)
x //= e
y //= e
(l, r, ans) = (0, 10 ** 10, -1)
while l <= r:
	m = (l + r) // 2
	if x * m <= a and y * m <= b:
		ans = m
		l = m + 1
	else:
		r = m - 1
print(ans * x, ans * y)


from fractions import gcd
(a, b, x, y) = map(int, input().split(' '))
g = gcd(x, y)
(x, y) = (x // g, y // g)
xmax = a // x
ymax = b // y
res = min(xmax, ymax)
print('%d %d' % (res * x, res * y))


(a, b, x, y) = map(int, input().split())
import math
n = math.gcd(x, y)
x = x // n
y = y // n
t = min(a // x, b // y)
print(x * t, end=' ')
print(y * t)


from math import gcd
(a, b, x, y) = map(int, input().split())
(x, y) = (x // gcd(x, y), y // gcd(x, y))
q = min(a // x, b // y)
print(x * q, y * q)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
(a, b, x, y) = map(int, input().split())
g = math.gcd(x, y)
x //= g
y //= g
m = min(a // x, b // y)
if x > a or y > b:
	print(0, 0)
	sys.exit(0)
l = 0
r = m
res = [0, 0]
while l <= r:
	mid = (l + r) // 2
	if x * mid <= a and y * mid <= b:
		res = [x * mid, y * mid]
		l = mid + 1
	else:
		r = mid - 1
print(*res)


import sys
from math import gcd
(a, b, x, y) = map(int, sys.stdin.readline().split())
gcdxy = gcd(x, y)
x //= gcdxy
y //= gcdxy
h = a // x
w = b // y
if h == 0 or w == 0:
	print(0, 0)
else:
	minhw = min(h, w)
	h = x * minhw
	w = y * minhw
	print(h, w)