题目描述

W 老师正在和他的粉丝 Menji 玩一个游戏。

桌上有 $n$ 张卡片，编号为 $1\sim n$，每张卡片有一个字母 $s_i$，其中 $s_i$ 为 $\texttt{X},\texttt{W},\texttt{M}$ 中的一个，且保证至少存在一个 $\texttt{W}$ 和至少一个 $\texttt{M}$。

W 老师和 Menji 轮流操作，W 老师先手，当轮到一名玩家操作时，他会选择一个区间 $[l,r](1\leq l\leq r\leq n)$，满足区间中不存在写有字母 $\texttt{X}$ 的卡片，然后拿走区间内所有卡片。

若在某次操作过后，所有的 $\texttt{W},\texttt{M}$ 卡片都已经被拿走，那么游戏平局，否则若某次操作后所有的 $\texttt{W}$ 都被拿走，那么 W 老师获胜，如果某次操作后所有的 $\texttt{M}$ 都被拿走，那么 Menji 获胜。

W 老师和 Menji 都是绝顶聪明的，现在给定所有的 $s_1\dots s_n$，请判断游戏的结果，若 W 老师获胜则输出 Water，如果 Menji 获胜则输出 Menji，如果平局则输出 Draw。

输入格式

本题含有多组测试数据。

第一行一个整数 $T(1\leq T\leq 10^5)$，表示测试数据数量。

对于每一组数据：

输入一行一个字符串 $n(2\leq |s| \leq 10^5)$，其中 $n=|s|$，$s_i$ 即为卡片 $i$ 上的字母。

输出格式

对于每一组数据，输出一行一个字符串，若 W 老师获胜则输出 Water，如果 Menji 获胜则输出 Menji，如果平局则输出 Draw。

6
WMW
MWM
WMWXMWM
WWWXMMMXWWW
MMMXWWWXMMM
WMWMWMWWMWW

Draw
Water
Draw
Menji
Water
Draw

提示

• 对于第一组数据，若 W 老师直接拿走所有的卡片，那么游戏是平局，否则 W 老师无法同时拿走两张写有 $\texttt{W}$ 的卡片，Menji 可以此时拿走写有 $\texttt{M}$ 的卡片并获胜。所以 W 老师一定会拿走所有卡片，游戏结果为平局。

• 对于第二组数据，W 老师直接拿走 $\texttt{W}$ 即可获胜。

题目来源

来自 2025 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2025）初赛。

题解等资源可在 https://gitlink.org.cn/thusaa/thupc2025pre/tree/master 查看。