UOJ Logo Universal Online Judge

UOJ

#68. 新年的桌游

统计

新年伊始,灰太狼又准备来入侵羊村啦!

为了抵御灰太狼,喜羊羊决定使用空城计。喜羊羊和美羊羊在羊村门口支起了桌子,装作若无其事的样子玩起了桌游。

灰太狼来到了羊村,看到喜羊羊和美羊羊玩得入神,居然忘记了抓羊,甚至分析明白了游戏规则。

游戏开始时,双方各持有若干张手牌,并且知道对方的手牌,一共有以下四种手牌:

  • 【灰太狼】:向对方使用后,对方必须立刻把一张【喜羊羊】扔进垃圾桶,否则对方输。
  • 【喜羊羊】:因为喜羊羊爱好和平,所以这张牌不能主动使用,只能用来防御【灰太狼】。
  • 【红太狼】:向对方使用后,对方必须立刻把一张【灰太狼】扔进垃圾桶,否则对方输。
  • 【美羊羊】:向对方使用后,由对方开始,双方必须轮流把一张【灰太狼】扔进垃圾桶,率先没有【灰太狼】的一方输。

喜羊羊很有绅士风度,所以总是让美羊羊先手。游戏的规则就是,从美羊羊开始,双方轮流进行自己的回合。每次进行自己的回合时,需要从自己的手牌中选出若干张(可以是 $0$ 张)以某种顺序排列好,然后按顺序一张一张出出去,最后结束这个回合。一张牌被出出去后必须立刻扔进垃圾桶,以后不能再次使用。每回合至多使用一张【灰太狼】类型的牌,而其余类型的牌没有次数限制。

如果双方在各进行了 $10^{30}$ 个回合之后依然没有分出胜负,则判为平局。

现在给出双方的初始手牌情况,灰太狼想要知道,如果双方均采取最优策略,最终的比赛结果会是什么。

灰太狼当然知道怎么做啦!但是他想考考你……

输入格式

第一行是一个正整数 $T$,表示数据的组数。

接下来是 $T$ 组数据,每组数据有两行,第一行是美羊羊(先手)的初始手牌,第二行是喜羊羊(后手)的初始手牌。

一个人手牌是用他的【灰太狼】、【喜羊羊】、【红太狼】、【美羊羊】数量,即四个空格隔开的自然数依次描述的。

输出格式

对于每组数据输出一行,如果最终为平局则输出 “Draw”,否则输出获胜者的名字(“Xiyangyang” 或 “Meiyangyang”)。

样例一

input

5
1 1 0 0
1 1 0 0
2 1 0 0
2 1 0 0
1 1 1 1
1 1 1 1
0 0 1 0
1 0 0 1
2 1 0 0
1 1 0 1

output

Draw
Meiyangyang
Meiyangyang
Xiyangyang
Draw

explanation

对于第一个样例,双方显然都有足够的【喜羊羊】来抵御对方的【灰太狼】,所以永远分不出胜负。

对于第二个样例,美羊羊显然可以在两个回合中出完两个【灰太狼】从而取胜。

对于第三个样例,美羊羊只需使用【红太狼】后使用【美羊羊】即可取胜。

对于第四个样例,喜羊羊可以抵御美羊羊的【红太狼】,美羊羊却无法抵御喜羊羊的【美羊羊】。

对于第五个样例,任何一方如果使用任何一张牌都会导致自己输,所以只能平局。

样例二

input

2
30 7 21 0
30 7 19 0
30 7 21 0
30 7 19 30

output

Meiyangyang
Draw

限制与约定

对于所有的数据,$T \leq 20$。

设 $n$ 为该个测试点中除 $T$ 外最大的数,则:

测试点编号 $n$ 其他限制
1$n \leq 1$
2$n \leq 2$
3$n \leq 30$保证双方均没有【美羊羊】和【红太狼】。
4$n \leq 30$保证双方均没有【美羊羊】。
5$n \leq 10^5$保证双方均没有【美羊羊】。
6$n \leq 10^9$保证双方均没有【美羊羊】和【红太狼】。
7$n \leq 30$
8$n \leq 30$
9$n \leq 10^5$
10$n \leq 10^9$

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

来源

UOJ Goodbye Jiawu

下载

样例数据下载