#include<bits/stdc++.h>
using namespace std;
#define elif else if
int n,r,i,j,k,len,jw;
int gj[1451]={1,1};
string a;
int main()
{
	scanf("%d%d",&n,&r);
	r%=26;
	for(i=0;i<n;i++)
	{
		cin>>a;
		len=a.size();
		for(j=0;j<len;j++)
		{
			a[j]+=r;
			if(a[j]>'Z')a[j]-=26;
		}
		cout<<a<<"\n";
		for(j=0;j<len;j++)
		{
			for(k=1;k<=gj[0];k++)
			{
				gj[k]=gj[k]*a[j]+jw;
				jw=gj[k]/100000;
				gj[k]%=100000;
			}
			if(jw)
			{
				gj[k]+=jw;
				gj[0]++;
				jw/=100000;
			}
			jw=0;
			printf("%d",gj[gj[0]]);
			for(k=gj[0]-1;k;k--)
			if(gj[k]<10)printf("0000%d",gj[k]);
			elif(gj[k]<100)printf("000%d",gj[k]);
			elif(gj[k]<1000)printf("00%d",gj[k]);
			elif(gj[k]<10000)printf("0%d",gj[k]);
			else printf("%d",gj[k]);
		}
		printf("\n");
		memset(gj,0,sizeof(gj));
		gj[0]=gj[1]=1;
	}
	return 0;
}