← 返回题目列表

Codeforces · 303/B

B. 矩形拼图 II

中文机器翻译题面 查看原题

给你一个矩形网格。该网格的大小为 n × m。让我们在网格上表示坐标系。因此,网格上的每个点都有坐标 — 一对整数 (x, y) (0 ≤ x ≤ n, 0 ≤ y ≤ m)。

你的任务是在网格 (x1, y1, x2, y2) 上找到一个最大子矩形,使其包含给定点 (x, y),且其长宽比正好为 (a, b)。换句话说,必须满足以下条件:0 ≤ x1 ≤ x ≤ x2 ≤ n,0 ≤ y1 ≤ y ≤ y2 ≤ m,$$\frac{x_{2}-x_{1}}{y_{2}-y_{1}}=\frac{a}{b}$$。

该子矩形的边应与轴平行。值 x1、y1、x2、y2 应该是整数。

如果有多个解,找到最接近 (x, y) 的矩形。这里的“最近”是指(x,y)与矩形中心之间的欧几里得距离尽可能小。如果仍有多个解决方案,请找到字典顺序最小的一个。这里的“字典序最小”意味着我们应该将子矩形视为整数序列(x1,y1,x2,y2),因此我们可以选择字典序最小的那个。

输入

第一行包含六个整数 n, m, x, y, a, b (1 ≤ n, m ≤ 109, 0 ≤ x ≤ n, 0 ≤ y ≤ m, 1 ≤ a ≤ n, 1 ≤ b ≤ m)。

输出

打印四个整数x1,y1,x2,y2,代表建立的左下点为(x1,y1),右上角点为(x2,y2)的子矩形。

示例

输入 #1

9 9 5 5 2 1

输出 #1

1 3 9 7

输入 #2

100 100 52 50 46 56

输出 #2

17 8 86 92