F=lambda s,e,m:s+''.join(map(str,m))+e
U=lambda x:eval(str(x))
def C(w,m,o,c,e):
 if[]==c:yield w,m;return
 for x in o:
  for i,y in enumerate(c):
   if len(w[x][1])<w[x][0]:W=U(w);M=U(m);W[x][1]=([y if~-x else(y,)]+W[x][1]if x else W[x][1]+[y]);M+=F(W[e][2],W[x][2],[y]),;yield from C(W,M,o,c[:i]+c[i+1:],e)
def V(w,m,t,c,B=0):
 if w[1][1][:len(j:=[i for i in w[1][1]if type(i)==tuple])]==j:
  for W,M in C(w,m,{0,2,3}-{c},[i for[i]in j],1):B=1;W,M=U(W),U(M);z=W[c][1];W[c][1]=[z[1:],z[:-1]][c<1];M+=F(W[c][2],'B',[t]),;W[1][1]=[t]+W[1][1][len(j):];yield W,M,1
  if B<1:
   w[c][1].remove(t)
   for W,M in C(w,m,{0,2,3}-{c},[t],c):yield W,M,0
def f(t):
 w,m=[{0:3,1:[],2:'A'},{0:5,1:[*range(1,6)],2:'B'},{0:3,1:[6,7,8],2:'C'},{0:3,1:[],2:'D'}],[];z=w[1][1]
 if z==t:return m
 T=t[:(r:=max(e)+1if(e:=[i for i in range(5)if t[i]-z[i]])else 5)]or t;W=z[:r];w[1][1]=z[r:]
 if(M:=W[:3][::-1]):w[3][1]+=M;m+=F('B','D',M[::-1]),
 if(M:=W[3:]):w[0][1]+=M;m+=F('B','A',M[::-1]),
 q=[(U(w),U(m),T)]
 while q:
  W,M,T=q.pop(0)
  if[]==T:return M
  if(O:=[i for i in[0,2,3]if W[i][1]and W[i][1][-(i<1)]==T[-1]]):
   for W,M,I in V(W,M,T[-1],O[0]):q+=(W,M,[T[:-1],T][I<1]),
  else:
   if(O:=[i for i in[0,2,3]if T[-1]in W[i][1]]):
    [c]=O;Z=W[c][1];S=[Z[:1],Z[-1:]][c<1];W[c][1]=[Z[1:],Z[:-1]][c<1]
    for W,M in C(W,M,{0,1,2,3}-{c},S,c):q+=(W,M,T),
 return m
 
print(f([1,2,3,4,5]))
print(f([2,1,3,4,5]))
print(f([1,4,3,8,5]))
print(f([4,3,5,2,1]))
print(f([8,6,3,1,7]))

Rj1sYW1iZGEgcyxlLG06cysnJy5qb2luKG1hcChzdHIsbSkpK2UKVT1sYW1iZGEgeDpldmFsKHN0cih4KSkKZGVmIEModyxtLG8sYyxlKToKIGlmW109PWM6eWllbGQgdyxtO3JldHVybgogZm9yIHggaW4gbzoKICBmb3IgaSx5IGluIGVudW1lcmF0ZShjKToKICAgaWYgbGVuKHdbeF1bMV0pPHdbeF1bMF06Vz1VKHcpO009VShtKTtXW3hdWzFdPShbeSBpZn4teCBlbHNlKHksKV0rV1t4XVsxXWlmIHggZWxzZSBXW3hdWzFdK1t5XSk7TSs9RihXW2VdWzJdLFdbeF1bMl0sW3ldKSw7eWllbGQgZnJvbSBDKFcsTSxvLGNbOmldK2NbaSsxOl0sZSkKZGVmIFYodyxtLHQsYyxCPTApOgogaWYgd1sxXVsxXVs6bGVuKGo6PVtpIGZvciBpIGluIHdbMV1bMV1pZiB0eXBlKGkpPT10dXBsZV0pXT09ajoKICBmb3IgVyxNIGluIEModyxtLHswLDIsM30te2N9LFtpIGZvcltpXWluIGpdLDEpOkI9MTtXLE09VShXKSxVKE0pO3o9V1tjXVsxXTtXW2NdWzFdPVt6WzE6XSx6WzotMV1dW2M8MV07TSs9RihXW2NdWzJdLCdCJyxbdF0pLDtXWzFdWzFdPVt0XStXWzFdWzFdW2xlbihqKTpdO3lpZWxkIFcsTSwxCiAgaWYgQjwxOgogICB3W2NdWzFdLnJlbW92ZSh0KQogICBmb3IgVyxNIGluIEModyxtLHswLDIsM30te2N9LFt0XSxjKTp5aWVsZCBXLE0sMApkZWYgZih0KToKIHcsbT1bezA6MywxOltdLDI6J0EnfSx7MDo1LDE6WypyYW5nZSgxLDYpXSwyOidCJ30sezA6MywxOls2LDcsOF0sMjonQyd9LHswOjMsMTpbXSwyOidEJ31dLFtdO3o9d1sxXVsxXQogaWYgej09dDpyZXR1cm4gbQogVD10Wzoocjo9bWF4KGUpKzFpZihlOj1baSBmb3IgaSBpbiByYW5nZSg1KWlmIHRbaV0teltpXV0pZWxzZSA1KV1vciB0O1c9els6cl07d1sxXVsxXT16W3I6XQogaWYoTTo9V1s6M11bOjotMV0pOndbM11bMV0rPU07bSs9RignQicsJ0QnLE1bOjotMV0pLAogaWYoTTo9V1szOl0pOndbMF1bMV0rPU07bSs9RignQicsJ0EnLE1bOjotMV0pLAogcT1bKFUodyksVShtKSxUKV0KIHdoaWxlIHE6CiAgVyxNLFQ9cS5wb3AoMCkKICBpZltdPT1UOnJldHVybiBNCiAgaWYoTzo9W2kgZm9yIGkgaW5bMCwyLDNdaWYgV1tpXVsxXWFuZCBXW2ldWzFdWy0oaTwxKV09PVRbLTFdXSk6CiAgIGZvciBXLE0sSSBpbiBWKFcsTSxUWy0xXSxPWzBdKTpxKz0oVyxNLFtUWzotMV0sVF1bSTwxXSksCiAgZWxzZToKICAgaWYoTzo9W2kgZm9yIGkgaW5bMCwyLDNdaWYgVFstMV1pbiBXW2ldWzFdXSk6CiAgICBbY109TztaPVdbY11bMV07Uz1bWls6MV0sWlstMTpdXVtjPDFdO1dbY11bMV09W1pbMTpdLFpbOi0xXV1bYzwxXQogICAgZm9yIFcsTSBpbiBDKFcsTSx7MCwxLDIsM30te2N9LFMsYyk6cSs9KFcsTSxUKSwKIHJldHVybiBtCiAKcHJpbnQoZihbMSwyLDMsNCw1XSkpCnByaW50KGYoWzIsMSwzLDQsNV0pKQpwcmludChmKFsxLDQsMyw4LDVdKSkKcHJpbnQoZihbNCwzLDUsMiwxXSkpCnByaW50KGYoWzgsNiwzLDEsN10pKQ==