Codeforces Round 183 (Div. 1)
B
Rectangle Puzzle II
Codeforces
1700
原题
← AC →
翻译中…

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*$, image.

翻译中…

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})$.

翻译中…

样例

Input #1
9 9 5 5 2 1
Output #1
1 3 9 7
InputCopy OutputCopy
Input #2
100 100 52 50 46 56
Output #2
17 8 86 92
InputCopy OutputCopy
题目信息
题号
303B
时间限制
2 s
内存限制
256 MB
标签
模拟
数学

题面与样例版权归 Codeforces 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。