背景

用糖果来引诱小朋友学习是最常用的手法，绵羊爸爸就是用糖果来引诱萌萌学习博弈的。

描述

他把糖果分成了两堆，一堆有A粒，另一堆有B粒。他让萌萌和他一起按照下面的规则取糖果：每次可以任意拿走其中一堆糖果；如果这时候另一堆糖果数目多于1粒，就把它任意分成两堆，否则就把剩下的一粒糖果取走并获得这次博弈的胜利。胜利者将获得所有的糖果。萌萌想要得到所有的糖果，而绵羊爸爸想把糖果留下以便下一次利用。现在由萌萌先取糖果，旁观的小朋友们想知道萌萌是否有必胜策略。

格式

输入格式

本题有多组测试数据（不超过100组）。每组数据包括两行，第一行为A，第二行为B。1 ≤ A,B ≤ 2^127。输入数据以一个 -1 结束。

输出格式

每组数据对应一行输出。如果萌萌获胜则输出"MengMeng"，否则输出"SheepDaddy"（不包括引号）。

样例1

样例输入1

1
2
2
3
-1
Copy

样例输出1

MengMeng
SheepDaddy
Copy

限制

所有测试点时限均为1000ms

    向手推大佬低头……Orz。这道题可以用SG函数找到规律：只要两堆石子都满足石子数对5取模余数为2或3，那么就是羊爸赢了。下面是SG函数的程序和AC代码。

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 30;
int sg[maxn * 2 + 5][maxn * 2 + 5];
bool vis[10000];
int main() {
	for(int i = 1; i <= maxn; ++i)
		sg[i][1] = sg[1][i] = 1;
	for(int sig = 4; sig <= maxn * 2; ++sig) 
		for(int j = 2; j < sig - 1; ++j){
			int p;
			int i = sig - j;
			for(int k = 1; k < i; ++k) {
				int l = i - k;
				vis[sg[k][l]] = 1;
			}
			for(int k = 1; k < j; ++k) {
				int l = j - k;
				vis[sg[k][l]] = 1;
			}
			for(p = 0; p < maxn; ++p)	{
				if(!vis[p]) break;
			}
			sg[i][j] = p;
			for(int k = 1; k < i; ++k) {
				int l = i - k;
				vis[sg[k][l]] = 0;
			}
			for(int k = 1; k < j; ++k) {
				int l = j - k;				vis[sg[k][l]] = 0;
			}
		}
	for(int i = 1; i <= maxn; ++i){
		for(int j = 1; j <= maxn; ++j)
			printf("%d ", sg[i][j] ? 1 : 0 );
		printf("\n");
	}
	return 0;
}

AC代码 19ms：

#include<cstdio>
#include<cstdlib>
using namespace std;

inline void read(int & ret) {
	char c = getchar();if(c == '-') exit(0);
	while(c > '9' || c < '0') c = getchar();
	while(c <= '9' && c >= '0') {
		if(c <= '9' && c >= '0') ret = c - '0';
		c = getchar(); 
	}
}

int main() {
	int a, b;
	while(1) {
		read(a), read(b);
		puts((a % 5 == 2 | a % 5 == 3)&(b % 5 == 2 | b % 5 == 3)?"SheepDaddy":"MengMeng");
	}
}