记录编号	343364	评测结果	AWWEEEEEEE
题目名称	Play with Power	最终得分	10
用户昵称	jmisnal	是否通过	未通过
代码语言	C++	运行时间	0.810 s
提交时间	2016-11-09 08:35:50	内存使用	13.16 MiB

#include <iostream>
#include <cstdio>
#include <cmath>
#define ll long long
using namespace std;
int f[100000][30];
bool mark[100000][30];
int n;
ll mpow(int a,int b)
{
	ll ret=1;
	for(int i=1;i<=b;i++)
	{
		ret*=a;
		if(ret>n)
			return n+1;
	}		
	return ret;
}
void dfs(int a,int b)
{
	if(b>=30)return;
//	cout<<"        "<<a<<' '<<b<<' '<<mark[a][b]<<' '<<mpow(a,b)<<endl;
	if(mark[a][b])
		return;
	
/*	if(b==1 && mpow(a,2)>n)
	{
//		cout<<"***"<<a<<' '<<b<<endl;
		mark[a][b]=1;
		f[a][b]=-1;
		return;
	}*/
	//if(b==1&&mpow(a.2))
	if(mpow(a,b)>n)
	{
//		cout<<"sb"<<a<<' '<<b<<endl;
		mark[a][b]=1;
		f[a][b]=1;
		return;
	}	
	if(a>=sqrt(n))
	{
		mark[a][b]=1;
		f[a][b]=1;
		return ;
	}
	mark[a][b]=1;	
	dfs(a+1,b);
/*	if(f[a+1][b]==-1)
	{
	//	cout<<'*'<<a<<' '<<b<<endl;
		f[a][b]=1;
		return;
	}*/ 
	dfs(a,b+1);
/*	if(f[a][b+1]==-1)
	{
		f[a][b]=1;
		return;
	}*/
	if(f[a][b+1]==-1||f[a+1][b]==-1)
		f[a][b]=1;
	else if(f[a][b+1]==2)
		f[a][b]=2;
	else f[a][b]=-1;
//	cout<<a<<' '<<b<<' '<<f[a][b]<<' '<<f[a+1][b]<<' '<<f[a][b+1]<<endl;
} 
int main()
{
//	freopen("abcd.in","r",stdin);
	freopen("play.in","r",stdin);
	freopen("play.out","w",stdout);
	int T;
	scanf("%d%d",&n,&T);
//	cout<<mark[2][2]<<endl;
//	n=log(100000000)/log(3);
	int C=log(n)/log(2);
	if(mpow(2,C)<=n)
		C++;
	for(int i=C;i<30;i++)
		f[1][i]=2,mark[1][i]=1;
	
		
	
	for(int i=sqrt(n);i>=2;i--)		//如果ai=1则missing 
	{
		int B=log(n)/log(i);
		mark[i][B]=1;
		if(mpow(i,B)==n)
		{
			f[i][B]=1;
		}
		else
		{
			int C=log(n)/log(i+1);
			f[i][B]=-1;
			if(B==C)
			{
				if(f[i+1][B]==-1)
					f[i][B]=1;
			}			
		}

	//	cout<<'*'<<i<<' '<<B<<' '<<f[i][B]<<endl;
	}

	int a,b;
	while(T--)
	{
	//	cout<<'a'<<endl;
		scanf("%d%d",&a,&b);
	/*	if(a==1)
		{
			ll sb=mpow(2,b);
			if(sb>n)
			{
					printf("Missing\n");
					continue;
			}										
		}*/
	//	cout<<a<<' '<<b<<endl;
		dfs(a,b);				
		if(f[a][b]==1)
			printf("Masha\n");
		else if(f[a][b]==-1)printf("Stas\n");
		else printf("Missing\n");
	//	cout<<f[a][b]<<endl;
	}
/*	cout<<f[129][1]<<' '<<f[129][2]<<endl;
	for(int i=100;i<=130;i++)
	cout<<i<<' '<<f[i][1]<<endl;
*/	return 0;
}