VK Cup 2015 - Finals, online mirror
G
Max and Min
Codeforces
2500
原题
← F→
翻译中…

Two kittens, Max and Min, play with a pair of non-negative integers $*x*$ and $*y*$. As you can guess from their names, kitten Max loves to maximize and kitten Min loves to minimize. As part of this game Min wants to make sure that both numbers, $*x*$ and $*y*$ became negative at the same time, and kitten Max tries to prevent him from doing so.

翻译中…

Each kitten has a set of pairs of integers available to it. Kitten Max has $*n*$ pairs of non-negative integers $(*a*_{*i*}, *b*_{*i*})$ ($1 ≤ *i* ≤ *n*$), and kitten Min has $*m*$ pairs of non-negative integers $(*c*_{*j*}, *d*_{*j*})$ ($1 ≤ *j* ≤ *m*$). As kitten Max makes a move, it can take any available pair $(*a*_{*i*}, *b*_{*i*})$ and add $*a*_{*i*}$ to $*x*$ and $*b*_{*i*}$ to $*y*$, and kitten Min can take any available pair $(*c*_{*j*}, *d*_{*j*})$ and subtract $*c*_{*j*}$ from $*x*$ and $*d*_{*j*}$ from $*y*$. Each kitten can use each pair multiple times during distinct moves.

翻译中…

Max moves first. Kitten Min is winning if at some moment both numbers $*a*$, $*b*$ are negative simultaneously. Otherwise, the winner of the game is kitten Max. Determine which kitten wins if both of them play optimally.

翻译中…

Input

翻译中…

The first line contains two integers, $*n*$ and $*m*$ ($1 ≤ *n*, *m* ≤ 100 000$) — the number of pairs of numbers available to Max and Min, correspondingly.

翻译中…

The second line contains two integers $*x*$, $*y*$ ($1 ≤ *x*, *y* ≤ 10^{9}$) — the initial values of numbers with which the kittens are playing.

翻译中…

Next $*n*$ lines contain the pairs of numbers $*a*_{*i*}, *b*_{*i*}$ ($1 ≤ *a*_{*i*}, *b*_{*i*} ≤ 10^{9}$) — the pairs available to Max.

翻译中…

The last $*m*$ lines contain pairs of numbers $*c*_{*j*}, *d*_{*j*}$ ($1 ≤ *c*_{*j*}, *d*_{*j*} ≤ 10^{9}$) — the pairs available to Min.

翻译中…

Output

翻译中…

Print «Max» (without the quotes), if kitten Max wins, or "Min" (without the quotes), if kitten Min wins.

翻译中…

Note

翻译中…

In the first test from the statement Min can respond to move $(2, 3)$ by move $(3, 10)$, and to move $(3, 2)$ by move $(10, 3)$. Thus, for each pair of Max and Min's moves the values of both numbers $*x*$ and $*y*$ will strictly decrease, ergo, Min will win sooner or later.

翻译中…

In the second sample test after each pair of Max and Min's moves both numbers $*x*$ and $*y*$ only increase, thus none of them will become negative.

翻译中…

样例

Input #1
2 2
42 43
2 3
3 2
3 10
10 3
Output #1
Min
InputCopy OutputCopy
Input #2
1 1
1 1
3 4
1 1
Output #2
Max
InputCopy OutputCopy
题目信息
题号
566G
时间限制
2 s
内存限制
256 MB
标签
计算几何

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