gistfile1.cpp

#include<iostream>
#include<vector>
#define fr(i,a,b) for(i=a;i<=b;i++)
using namespace std;
long long a,m,p,q,r,s,ans,pw[100],i,ca=0,now,tot;
vector<long long> len,len2;
vector<char> ty,ty2;
long long atleast(long long value){
	if(value<=0)
		return 0;
	return (value-1)/a+1;
}
void put(long long tt,long long ch){
	if(tt>0)
		if(ty2.size()>0&&ty2[ty2.size()-1]==ch)
			len2[len2.size()-1]+=tt;
		else{
			len2.push_back(tt);
			ty2.push_back(ch);
		}
}
bool check(long long p,long long q){
	int i;
	fr(i,0,(int)len2.size()-1)
		if(ty2[i]=='A'){
			p+=len2[i]*a;
			q+=len2[i]*a;
			if(q>s)
				return false;
		}
		else{//check
			p*=pw[len2[i]];
			q*=pw[len2[i]];
			if(q>s)
				return false;
		}
	return p>=r&&q<=s;
}
void update(){
	long long sum=0;
	fr(i,0,(int)len2.size()-1)
		sum+=len2[i];
	if(sum>ans)
		return;
	if(ans==sum)
		fr(i,0,(int)min(len2.size(),len.size())-1)
			if(len2[i]!=len[i]||ty[i]!=ty2[i])
				if(ty[i]!=ty2[i]){
					if(ty[i]<ty2[i])
						return;
					break;
				}
				else
					if(ty[i]=='A'){
						if(len[i]>len2[i])
							return;
						break;
					}
					else{
						if(len[i]<len2[i])
							return;
						break;
					}
	ans=sum;
	len=len2;
	ty=ty2;
}
void work(long long tot,long long p,long long q,long long r,long long s){
/*	int i,j,k;
	for(i=tot;i>=0;i--)
		fr(k,0,1){
			len2.clear();
			ty2.clear();
			put(atleast(r/pw[tot]-p),'A');
			for(j=tot-1;j>=i;j--){
				put(1,'M');
				put(atleast((r/pw[j])%m),'A');
			}
			put(k,'A');
			put(i,'M');
			if(check(p,q))
				update();
		}*/
	len2.clear();
	ty2.clear();
	if(p*pw[tot]>=r){
		put(tot,'M');
		if(check(p,q))
			update();
		return;
	}
	long long tmp=atleast(r-p*pw[tot]);
/*	put(tmp/pw[tot],'A');
	for(i=tot-1;i>=0;i--){
		put(1,'M');
		put(tmp/pw[i]%m,'A');
	}
	if(check(p,q))
		update();*/

	long long i,j,k;
	for(i=tot;i>=0;i--)
		fr(k,0,1){
			len2.clear();
			ty2.clear();
			put(tmp/pw[tot],'A');
			for(j=tot-1;j>=i;j--){
				put(1,'M');
				put(tmp/pw[j]%m,'A');
			}
			put(k,'A');
			put(i,'M');
			if(check(p,q))
				update();
		}
}
int main(){
	cin>>a>>m>>p>>q>>r>>s;
	while(a+m+p+q+r+s>0){
		cout<<"Case "<<++ca<<":";
		if(r<=p&&q<=s){
			cout<<" empty"<<endl;
			cin>>a>>m>>p>>q>>r>>s;
			continue;
		}
		ans=2000000000;
		now=1;
		tot=0;
		while(q<=s/now){
			pw[tot]=now;
			work(tot,p,q,r,s);
			if(m==1)
				break;
			now=now*m;
			tot++;
		}
		if(ans==2000000000)
			cout<<" impossible"<<endl;
		else{
			fr(i,0,(int)len.size()-1)
				cout<<" "<<len[i]<<ty[i];
			cout<<endl;
		}			
		cin>>a>>m>>p>>q>>r>>s;
	}
}