A,B=gets,gets.split L=[] R=[] U=[] D=[] N=[] C=[] S=[] O=[0]*81 z='A' (0..324).map{|j|U<s,j,c,cf,n{ j<81 ? (z==A[j]?(0..8).map{|i|X[s-1-i,j+1,c+[i],cf+[1+j,1+81+27*i+j/9,1+81+27*i+9+j%9,1+81+27*i+18+j/3%3+j/27*3],n+[i+1]]}:X[s,j+1,c,cf,n+[0]]if s>=0) : (h=U.size;cf.uniq.sort.map{|l|N<c{L[R[c]]=L[c];R[L[c]]=R[c];i=D[c];(j=R[i];(U[D[j]]=U[j];D[U[j]]=D[j];S[C[j]]-=1;j=R[j])while j!=i;i=D[i])while i!=c} Z=->c{i=U[c];(j=L[i];(S[C[j]]+=1;U[D[j]]=j;D[U[j]]=j;j=L[j])while j!=i;i=U[i])while i!=c;L[R[c]]=c;R[L[c]]=c} B.map{|k|X[k.to_i,0,[],[],[]];z=z=='Z'?'a':z.next} s=->k{ c=R[0] c<1 ? ($><<(O[0,k].map{|s|N[s]}.transpose.map &:max)*"") : (g=S[b=c];g=S[b=c]if S[c]