记录编号	343214	评测结果	AAAAAAAAAA
题目名称	Play with Power	最终得分	100
用户昵称	Sky_miner	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2016-11-09 05:56:23	内存使用	3.61 MiB

#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
	x=0;char ch;bool flag = false;
	while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
	while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
int N,A,B,pw[51],cnt=0;
bool can(double a,int b,double n){
	int nt = (int)n;
	for(int i=1;i<=b;++i) n/=a;
	if(n == 1){
		int x = 1;
		for(int i=1;i<=b;++i) x*=a;
		if(x >= nt) return true;
		else return false;
	}else return n > 1;
}
char f[100010][51];
void dfs(int a,int b,int k){
	if(a < 1 && b < 1) return;
	if(k == 0){
		if(f[a+1][b] == 1 && f[a][b+1] == 1) k = 2;
		else return;
	}f[a][b] = k;
	if(a >= 0 && f[a-1][b] == 0) dfs(a-1,b,k-1);
	if(b >= 0 && f[a][b-1] == 0) dfs(a,b-1,k-1);
}
inline void pre_work(){
	pw[1] = (int)sqrt(N) + 1;
	pw[2] = (int)sqrt(N);int i=3;
	if(pw[2] <= 2){cnt = pw[2];goto lable2;}
	pw[3] = pw[2];
	while(pw[i]>=2){
		//printf("%d %d %d\n",i,pw[i],N);
		if (can(pw[i],i,N)){++i;pw[i]=pw[i-1];}
		else --pw[i];
	}
	cnt = i;//printf("%d %d %d\n",pw[1],pw[2],cnt);
lable2:
	--cnt;
	for(i=2;i<=cnt;++i){
		if(pw[i] != pw[i+1]){
			dfs(pw[i],i,2);
			for(int j=pw[i+1]+1;j<pw[i];++j) dfs(j,i+1,1);
		}else dfs(pw[i]+1,i,1);
	}
}

int main(){
	freopen("play.in","r",stdin);
	freopen("play.out","w",stdout);
	read(N);
	pre_work();
	//for(int k=1;k<=cnt;++k) printf("%d ",pw[k]);puts("");
	// for(int i=1;i<=20;++i){
	// 	for(int j=1;j<=20;++j){
	// 		printf("%d ",f[i][j]);
	// 	}puts("");
	// }
	int m;read(m);
	while(m--){
		read(A);read(B);
		if(A == 1 && B > cnt) puts("Missing");
		else{
			if(B == 1 && A > sqrt(N)){
				if(((N-A)&1) == 1) puts("Masha");
				else puts("Stas");
			}else{
				if(f[A][B] == 1) puts("Masha");
				else if(f[A][B] == 2) puts("Stas");
				else puts("Missing");
			}
		}
	}
	getchar();getchar();
	fclose(stdin);fclose(stdout);
	return 0;
}