#P4644. Max and Min

Max and Min

题目描述

有两只特别珂爱的小猫,一个叫做 Min,另一个叫做 Max。今天,Min 和 Max 来玩一个游戏。

游戏开始时,有两个整数。每只猫都有许多组可以用来玩游戏的数对。小猫 Max 有 nn 对非负整数 (ai,bi)(a_i,b_i),同理,小猫 Min 也有 mm 对非负整数 (cj,dj)(c_j,d_j)

当轮到小猫 Max 走的时候,它可以选择任何一对 (ai,bi)(a_i,b_i) 并将 xx 加上 aia_iyy 加上 bib_i;当轮到 Min 的时候,它可以选择任何可用的对 (cj,dj)(c_j,d_j) 并把 xx 减去 cjc_j,把 yy 减去 djd_j

Max 和 Min 可以在不同的移动过程中多次使用每一对。Max 先开始游戏。

如果在某个时刻 x,yx,y 两个数字同时为负整数,那么 Min 就获胜了!否则,为 Max 获胜。

这两只珂爱的小猫想让你告诉它们,到底谁会赢?假设两只小猫都足够聪明,都会以最优方法来走。

输入格式

输入的第一行包含两个整数,分别为 nnmm。对应着 Max 和 Min 可用的数字对的数目。

第二行包含两个整数 x,yx,y 这两个数代表小猫玩的数字的初始值。

接下来的 nn 行包含数对 ai,bia_i,b_i,代表小猫 Max 可用的对。

最后的 mm 行包含数对 ci,dic_i,d_i,代表小猫 Min 可用的对。

1n,m1000001\le n,m\le1000001x,y1091\le x,y\le10^{9}1ai,bi,ci,di1091\le a_{i},b_{i},c_{i},d_{i}\le10^{9}

输出格式

如果小猫 Max 赢了,则输出 Max,如果 Min 赢了,则输出 Min

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

Min 可以通过移动 (3,10)(3,10) 对 Max 移动 (2,3)(2,3) 做出响应,并通过移动 (10,3)(10,3) 来响应 Max 的移动 (3,2)(3,2) 的方案。因此,对于每一对最大值和最小值的移动,数字 xxyy 的值都将严格减小,因此,Min 迟早会赢。

1 1
1 1
3 4
1 1
Max

每对最大值和最小值移动后,数字 xxyy 只会增加,因此它们都不会变为负值。