记录编号	344077	评测结果	AAAAAAAAAA
题目名称	Play with Power	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	0.098 s
提交时间	2016-11-09 21:00:34	内存使用	0.73 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=10015,maxm=41;
bool win[maxn+5][maxm+5];int n;
bool Rabit_get(int x,int k){
	if(!x)return false;
	int res=1;
	while(k){
		if(k&1){
			if(res*1ll*x>n)return true;
			res*=x;
		}
		k>>=1;
		if(x*1ll*x>n&&k)return true;
		x*=x;
	}	
	return false;
}
void Rabit_pre(){
	int i,j;
	for(i=maxn-2;i;i--) 
	for(j=maxm-2;j;j--)
		win[i][j]=((!Rabit_get(i+1,j))&&!win[i+1][j])||((!Rabit_get(i,j+1))&&(!win[i][j+1]));
}
void Rabit_main(){
	scanf("%d",&n);int tt,a,b;scanf("%d",&tt);
	Rabit_pre();
	for(int i=1;i<=tt;i++){
		scanf("%d%d",&a,&b);
		if(Rabit_get(a,b+1)&&Rabit_get(a+1,b))puts("Stas");
		else if(a==1&&Rabit_get(a+1,b))puts("Missing");
		else if(b==1){if((n-a)&1)puts("Masha");else puts("Stas");}
		else if(win[a][b])puts("Masha");else puts("Stas");
	}
}
int main(){
#define _Rabit _RABIT
#ifdef _Rabit
	freopen("play.in","r",stdin);
	freopen("play.out","w",stdout);
#endif
	Rabit_main();
#ifndef _Rabit
	getchar(),getchar();
#endif
	fclose(stdin);fclose(stdout);
	return 0;
}