You are given a rectangle grid. That grid's size is n × m. Let's denote the coordinate system on the grid. So, each point on the grid will have coordinates — a pair of integers (x, y) (0 ≤ x ≤ n, 0 ≤ y ≤ m).

Your task is to find a maximum sub-rectangle on the grid (x_1, y_1, x_2, y_2) so that it contains the given point (x, y), and its length-width ratio is exactly (a, b). In other words the following conditions must hold: 0 ≤ x_1 ≤ x ≤ x_2 ≤ n, 0 ≤ y_1 ≤ y ≤ y_2 ≤ m, $\frac{x_{2} - x_{1}}{y_{2} - y_{1}} = \frac{a}{b}$.

The sides of this sub-rectangle should be parallel to the axes. And values x_1, y_1, x_2, y_2 should be integers. [Image] 

If there are multiple solutions, find the rectangle which is closest to (x, y). Here "closest" means the Euclid distance between (x, y) and the center of the rectangle is as small as possible. If there are still multiple solutions, find the lexicographically minimum one. Here "lexicographically minimum" means that we should consider the sub-rectangle as sequence of integers (x_1, y_1, x_2, y_2), so we can choose the lexicographically minimum one.


-----Input-----

The first line contains six integers n, m, x, y, a, b (1 ≤ n, m ≤ 10^9, 0 ≤ x ≤ n, 0 ≤ y ≤ m, 1 ≤ a ≤ n, 1 ≤ b ≤ m).


-----Output-----

Print four integers x_1, y_1, x_2, y_2, which represent the founded sub-rectangle whose left-bottom point is (x_1, y_1) and right-up point is (x_2, y_2).


-----Examples-----
Input
9 9 5 5 2 1

Output
1 3 9 7

Input
100 100 52 50 46 56

Output
17 8 86 92

Difficulty: MEDIUM_HARD
Tags: Mathematics

Implementation

Starter code:

Solutions:
import math
(n, m, x, y, a, b) = map(int, input().split())
gcd = math.gcd(a, b)
a //= gcd
b //= gcd
max_ratio = min(n // a, m // b)
a *= max_ratio
b *= max_ratio
x1 = max(0, min(x - (a + 1) // 2, n - a))
y1 = max(0, min(y - (b + 1) // 2, m - b))
print(x1, y1, x1 + a, y1 + b)


import sys
from fractions import gcd
with sys.stdin as fin, sys.stdout as fout:
	(n, m, x, y, a, b) = map(int, next(fin).split())
	d = gcd(a, b)
	a //= d
	b //= d
	k = min(n // a, m // b)
	w = k * a
	h = k * b
	x1 = x - (w + 1) // 2
	y1 = y - (h + 1) // 2
	x1 = min(x1, n - w)
	y1 = min(y1, m - h)
	x1 = max(x1, 0)
	y1 = max(y1, 0)
	print(x1, y1, x1 + w, y1 + h, file=fout)


import sys
from fractions import gcd
with sys.stdin as fin, sys.stdout as fout:
	(n, m, x, y, a, b) = map(int, next(fin).split())
	d = gcd(a, b)
	a //= d
	b //= d
	k = min(n // a, m // b)
	w = k * a
	h = k * b
	best = tuple([float('inf')] * 3)
	for add1 in (0, 1):
		for add2 in (0, 1):
			x1 = x - w // 2 - add1
			y1 = y - h // 2 - add2
			cur = ((2 * x1 + w - 2 * x) ** 2 + (2 * y1 + h - 2 * y) ** 2, x1, y1)
			if cur < best:
				best = cur
	(x1, y1) = best[1:]
	x1 = min(x1, n - w)
	y1 = min(y1, m - h)
	x1 = max(x1, 0)
	y1 = max(y1, 0)
	print(x1, y1, x1 + w, y1 + h)


from fractions import gcd
(n, m, x, y, a, b) = map(int, input().split())
r = gcd(a, b)
(a, b) = (a // r, b // r)
r = min(n // a, m // b)
(a, b) = (a * r, b * r)
(cx, cy) = ((a + 1) // 2, (b + 1) // 2)
(dx, dy) = (min(n - a, max(cx, x) - cx), min(m - b, max(cy, y) - cy))
print(dx, dy, a + dx, b + dy)


from fractions import gcd
(n, m, x, y, a, b) = list(map(int, input().split()))
g = gcd(a, b)
(a, b) = (a // g, b // g)
k = min(n // a, m // b)
(a, b) = (k * a, k * b)
(x1, x2) = (x - (a - a // 2), x + a // 2)
(y1, y2) = (y - (b - b // 2), y + b // 2)
d = max(0, 0 - x1)
(x1, x2) = (x1 + d, x2 + d)
d = max(0, x2 - n)
(x1, x2) = (x1 - d, x2 - d)
d = max(0, 0 - y1)
(y1, y2) = (y1 + d, y2 + d)
d = max(0, y2 - m)
(y1, y2) = (y1 - d, y2 - d)
print(' '.join(map(str, [x1, y1, x2, y2])))


from fractions import gcd
(n, m, x, y, a, b) = list(map(int, input().split()))
k = gcd(a, b)
a //= k
b //= k
times = min(n // a, m // b)
a *= times
b *= times
x1 = x - (a + 1) // 2
y1 = y - (b + 1) // 2
if x1 < 0:
	x1 = 0
if y1 < 0:
	y1 = 0
if x1 + a > n:
	x1 -= x1 + a - n
if y1 + b > m:
	y1 -= y1 + b - m
print(x1, y1, x1 + a, y1 + b)