← 返回题目列表

Codeforces · 566/G

G. 最大和最小

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

两只小猫 Max 和 Min 正在玩一对非负整数 x 和 y。从它们的名字中你可以猜出,小猫 Max 喜欢最大化,小猫 Min 喜欢最小化。作为这个游戏的一部分,Min 想要确保 x 和 y 这两个数字同时变为负数,而小猫 Max 试图阻止他这样做。

每只小猫都有一组可用的整数对。 Kitten Max 有 n 对非负整数 (ai, bi) (1 ≤ i ≤ n),kitten Min 有 m 对非负整数 (cj, dj) (1 ≤ j ≤ m)。当小猫 Max 采取行动时,它可以采用任何可用的对 (ai, bi) 并将 ai 添加到 x,将 bi 添加到 y,而小猫 Min 可以采用任何可用的对 (cj, dj) 并从 x 中减去 cj,从 y 中减去 dj。每只小猫都可以在不同的动作中多次使用每一对。

最大移动数先行。如果在某个时刻 a、b 同时为负数,Kitten Min 获胜。否则,游戏的获胜者是小猫麦克斯。如果两只小猫都发挥最佳,确定哪只小猫获胜。

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 100 000) — 相应地,可用于 Max 和 Min 的数字对的数量。

第二行包含两个整数 x, y (1 ≤ x, y ≤ 109) — 小猫正在玩的数字的初始值。

接下来的 n 行包含数字对 ai, bi (1 ≤ ai, bi ≤ 109) — Max 可以使用的数字对。

最后 m 行包含数字对 cj, dj (1 ≤ cj, dj ≤ 109) — 这些对可用于 Min。

输出

如果小猫 Max 获胜,则打印“Max”(不带引号);如果小猫 Min 获胜,则打印“Min”(不带引号)。

示例

输入 #1

2 2
42 43
2 3
3 2
3 10
10 3

输出 #1

Min

输入 #2

1 1
1 1
3 4
1 1

输出 #2

Max

注意

在语句 Min 的第一个测试中,Min 可以通过 move (3, 10) 响应 move (2, 3),并通过 move (10, 3) 响应 move (3, 2)。因此,对于每一对 Max 和 Min 的移动,数字 x 和 y 的值都将严格减小,因此 Min 迟早会获胜。

在每对 Max 和 Min 的移动之后的第二个样本测试中,数字 x 和 y 都只会增加,因此它们都不会变为负数。