#P2172. Mario填格子

    ID: 1196 传统题 2000ms 259MiB 尝试: 377 已通过: 76 难度: 8 上传者: 标签>CF2400提高+/省选-Miller–RabinPollard–Rho快速幂快速乘防溢出矩阵构造约数个数乘积公式对称性分析

Mario填格子

题目描述

《超级马里奥兄弟》是任天堂于 1985 年出品的著名横版过关游戏,作为 1983 年游戏《马里奥兄弟》的续作在 FC 红白机上推出。在游戏《超级马里奥兄弟》中,玩家控制马里奥从库巴手上设法营救 Peach 公主。

今年是《超级马里奥兄弟》发行 25 周年了,任天堂推出了 25 周年纪念合集。lqp 也想来凑热闹,他开发了一个小游戏,叫做「Mario 填格子」。游戏是这样的,Boss Wario 给出了一个 3×33\times 3 的小格子,在左上角填上了 mm,右下角填上了 nn。

现在开始倒计时了,你必须给剩余的几个格子填上一些正整数,对于每个格子(格子里的数是 xx)满足:如果它左边相邻有一个数 yy,那么 y∣xy|x(表示 yy 整除 xx)。如果它上面相邻有一个数 zz,那么 z∣xz|x。不存在和它填有相同数字的格子。

比如下面就是一个 m=1,n=36m=1,n=36 的满足条件的填法:

1 2 4
3 6 12
9 18 36

输入格式

输入包含若干行,以 EOF 结束。

每行包含两个正整数 mm 和 nn,分别是左上角的数字和右下角的数字。

输出格式

如果 Mario 能够获胜,输出 Mario_wins!,否则输出 Wario_wins!。每个数据输出一个空行。

样例输入

1 36
4 36 

样例输出

Mario_wins!

Wario_wins!

数据规模与约定

10%10\% 数据满足:1≤m,n≤91\leq m,n\leq 9。

30%30\% 数据满足:1≤m,n≤1001\leq m,n\leq 100。

50%50\% 数据满足:1≤m,n≤1×1051\leq m,n\leq 1\times 10^5。

100%100\% 数据满足:最多 1010 组测试数据,1≤m,n≤10171\leq m,n\leq 10^{17}。

其中有 10%10\% 数据 n=m×ptn=m\times p^{t}。