CF48E.Ivan the Fool VS Gorynych the Dragon

Once upon a time in a kingdom far, far away… Okay, let’s start at the point where Ivan the Fool met Gorynych the Dragon. Ivan took out his magic sword and the battle began. First Gorynych had h heads and t tails. With each strike of the sword Ivan can either cut off several heads (from 1 to n, but not more than Gorynych has at the moment), or several tails (from 1 to m, but not more than Gorynych has at the moment). At the same time, horrible though it seems, Gorynych the Dragon can also grow new heads and tails. And the number of growing heads and tails is determined uniquely by the number of heads or tails cut by the current strike. When the total number of heads and tails exceeds R, Gorynych the Dragon strikes its final blow and destroys Ivan the Fool. That’s why Ivan aims to cut off all the dragon’s heads and tails as quickly as possible and win. The events can also develop in a third way: neither of the opponents can win over the other one and they will continue fighting forever.

The tale goes like this; easy to say, hard to do. Your task is to write a program that will determine the battle’s outcome. Consider that Ivan strikes consecutively. After each blow Gorynych grows a number of new heads and tails depending on the number of cut ones. Gorynych the Dragon is defeated if after the blow he loses all his heads and tails and can’t grow new ones. Ivan fights in the optimal way (fools are lucky), i.e.

• if Ivan can win, he wins having struck the least number of blows;
• if it is impossible to defeat Gorynych, but is possible to resist him for an infinitely long period of time, then that’s the strategy Ivan chooses;
• if Gorynych wins in any case, Ivan aims to resist him for as long as possible.

很久很久以前，在一个遥远的王国里……好吧，我们从愚者伊万遇见戈里尼奇巨龙的那一刻开始讲起。伊万拔出了他的魔法剑，战斗就此展开。起初，戈里尼奇巨龙有 $h$ 个头和 $t$ 条尾巴。每次挥剑，伊万可以选择斩下若干个头（数量为 $1$ 至 $n$ 之间的整数，但不能超过戈里尼奇当前拥有的头数），或者斩下若干条尾巴（数量为 $1$ 至 $m$ 之间的整数，但不能超过戈里尼奇当前拥有的尾巴数）。与此同时，尽管听起来十分可怕，戈里尼奇巨龙也能长出新的头和尾巴。而新长出的头与尾巴的数量，由本次攻击所斩下的头数或尾数唯一确定。一旦头与尾巴的总数超过 $R$，戈里尼奇巨龙便会发动致命一击，将愚者伊万彻底消灭。正因如此，伊万的目标是尽快斩尽巨龙的所有头与尾巴，从而赢得胜利。当然，战局也可能走向第三种结局：双方均无法战胜对方，战斗将无限持续下去。

故事虽如此，做起来却殊非易事。你的任务是编写一个程序，用以判定这场战斗的最终结果。假设伊万连续不断地发动攻击；每次攻击之后，戈里尼奇会依据本次被斩下的头数或尾数，生长出相应数量的新头与新尾巴。若某次攻击后，戈里尼奇失去了全部的头与尾巴，且无法再长出新的头与尾巴，则视为被击败。伊万采取最优策略（愚者自有天佑），即：

• 若伊万能够获胜，则他将以最少的攻击次数取胜；
• 若无法击败戈里尼奇，但可以无限期地抵抗下去，则他将选择这种策略；
• 若无论怎样戈里尼奇终将获胜，则伊万将尽可能延长抵抗时间。

The first line contains three integers h, t and R (0 ≤ h, t, R ≤ 200, 0 < h + t ≤ R) which represent the initial numbers of Gorynych’s heads and tails and the largest total number of heads and tails with which Gorynych the Dragon does not yet attack. The next line contains integer n (1 ≤ n ≤ 200). The next n contain pairs of non-negative numbers "h__i t__i" which represent the number of heads and the number of tails correspondingly, that will grow if Gorynych has i heads (1 ≤ i ≤ n) cut. The next line contains an integer m (1 ≤ m ≤ 200) and then — the description of Gorynych’s behavior when his tails are cut off in the format identical to the one described above. All the numbers in the input file do not exceed 200.

第一行包含三个整数 $h$、$t$ 和 $R$（$0 \le h, t, R \le 200$，且 $0 < h + t \le R$），分别表示戈里内奇龙初始的头数、尾数，以及其尚未发动攻击时头与尾总数的最大值。
第二行包含一个整数 $n$（$1 \le n \le 200$）。
接下来的 $n$ 行每行包含一对非负整数 “$h_i\ t_i$”，表示若砍掉戈里内奇龙 $i$ 个头（$1 \le i \le n$），则将分别长出 $h_i$ 个头和 $t_i$ 条尾。
下一行包含一个整数 $m$（$1 \le m \le 200$），随后是戈里内奇龙在尾被砍断时的行为描述，格式与上述头被砍断时的描述完全相同。
输入文件中的所有数字均不超过 $200$。

Print "Ivan" (without quotes) in the first line if Ivan wins, or "Zmey" (that means a dragon in Russian) if Gorynych the Dragon wins. In the second line print a single integer which represents the number of blows Ivan makes. If the battle will continue forever, print in the first line "Draw".

如果伊万获胜，则在第一行输出“Ivan”（不带引号）；如果龙戈里内奇获胜，则输出“Zmey”（俄语中“龙”的意思）。第二行输出一个整数，表示伊万所击出的攻击次数。如果战斗将永远持续下去，则在第一行输出“Draw”。