E=enumerate
R=range
X=max
from itertools import*
def C(l,L,H):
 q=[([a],[i])for i,a in E(l)if a<=L]
 while q:
  A,I=q.pop(0)
  if(L>=sum(A))*(H<1or sum(A)==L):yield(tuple(A),I)
  for i,a in E(l[X(I)+1:],X(I)+1):q+=[(T:=A+[a],I+[i])]*(sum(T)<=L)
def P(b,l,Q,t):
 for i,a in E(b):
  if''in a:
   F=0;B,Y=eval(str(b)),[]
   for g in([[j for j,_ in b]for c,b in groupby(E(a),key=lambda x:x[1]=='')if c]):
    if(O:=[*C(l,len(g),t)]):
     F,d=1,{}
     for J,K in O:d[J]=K
     O=[*d.items()];M=X(sum(A)for A,_ in O);V,I=min([(o,p)for o,p in O if sum(o)==M],key=lambda x:len(x[0]));Y+=I
     for v in V:
      Q+=1
      for _ in R(v):B[i][g.pop(0)]=chr(Q)
   if F+t:return(B,[y for x,y in E(l)if~-(x in Y)],Q)
def f(l):
 I=[1,X(l)][X(l)>10];Q=96
 while I:
  q=[(B:=[['']*I]*10,[*l],96)];S=[B]
  while q:
   b,L,Q=q.pop(0)
   if[]==L:return b
   if(C:=P(b,L,Q,1))and~-(C in S):q+=C,;S+=C,
   if(C:=P([*map(list,zip(*b))],L,Q,0)):
    B,L,Q=C;B=[*map(list,zip(*B))]
    if~-(B in S):q+=(B,L,Q),;S+=B,
  I+=1
 
print(f([8, 8, 8, 3]))
print(f([2,2,4,2,2,4,4,4]))
print(f([12,2,2,2,3,4,4,8,8]))
print(f([4,4,4,4,4,4,4,4,4,4,4,4]))
print(f([4,4,4,4,4,4,3,3,3,2,2,2,1]))

RT1lbnVtZXJhdGUKUj1yYW5nZQpYPW1heApmcm9tIGl0ZXJ0b29scyBpbXBvcnQqCmRlZiBDKGwsTCxIKToKIHE9WyhbYV0sW2ldKWZvciBpLGEgaW4gRShsKWlmIGE8PUxdCiB3aGlsZSBxOgogIEEsST1xLnBvcCgwKQogIGlmKEw+PXN1bShBKSkqKEg8MW9yIHN1bShBKT09TCk6eWllbGQodHVwbGUoQSksSSkKICBmb3IgaSxhIGluIEUobFtYKEkpKzE6XSxYKEkpKzEpOnErPVsoVDo9QStbYV0sSStbaV0pXSooc3VtKFQpPD1MKQpkZWYgUChiLGwsUSx0KToKIGZvciBpLGEgaW4gRShiKToKICBpZicnaW4gYToKICAgRj0wO0IsWT1ldmFsKHN0cihiKSksW10KICAgZm9yIGcgaW4oW1tqIGZvciBqLF8gaW4gYl1mb3IgYyxiIGluIGdyb3VwYnkoRShhKSxrZXk9bGFtYmRhIHg6eFsxXT09JycpaWYgY10pOgogICAgaWYoTzo9WypDKGwsbGVuKGcpLHQpXSk6CiAgICAgRixkPTEse30KICAgICBmb3IgSixLIGluIE86ZFtKXT1LCiAgICAgTz1bKmQuaXRlbXMoKV07TT1YKHN1bShBKWZvciBBLF8gaW4gTyk7VixJPW1pbihbKG8scClmb3IgbyxwIGluIE8gaWYgc3VtKG8pPT1NXSxrZXk9bGFtYmRhIHg6bGVuKHhbMF0pKTtZKz1JCiAgICAgZm9yIHYgaW4gVjoKICAgICAgUSs9MQogICAgICBmb3IgXyBpbiBSKHYpOkJbaV1bZy5wb3AoMCldPWNocihRKQogICBpZiBGK3Q6cmV0dXJuKEIsW3kgZm9yIHgseSBpbiBFKGwpaWZ+LSh4IGluIFkpXSxRKQpkZWYgZihsKToKIEk9WzEsWChsKV1bWChsKT4xMF07UT05Ngogd2hpbGUgSToKICBxPVsoQjo9W1snJ10qSV0qMTAsWypsXSw5NildO1M9W0JdCiAgd2hpbGUgcToKICAgYixMLFE9cS5wb3AoMCkKICAgaWZbXT09TDpyZXR1cm4gYgogICBpZihDOj1QKGIsTCxRLDEpKWFuZH4tKEMgaW4gUyk6cSs9Qyw7Uys9QywKICAgaWYoQzo9UChbKm1hcChsaXN0LHppcCgqYikpXSxMLFEsMCkpOgogICAgQixMLFE9QztCPVsqbWFwKGxpc3QsemlwKCpCKSldCiAgICBpZn4tKEIgaW4gUyk6cSs9KEIsTCxRKSw7Uys9QiwKICBJKz0xCiAgCnByaW50KGYoWzgsIDgsIDgsIDNdKSkKcHJpbnQoZihbMiwyLDQsMiwyLDQsNCw0XSkpCnByaW50KGYoWzEyLDIsMiwyLDMsNCw0LDgsOF0pKQpwcmludChmKFs0LDQsNCw0LDQsNCw0LDQsNCw0LDQsNF0pKQpwcmludChmKFs0LDQsNCw0LDQsNCwzLDMsMywyLDIsMiwxXSkp