from random import*
from itertools import*
R=range
def U(D,B,x,y,X,Y):
 try:D[B[x][y]]=D.get(B[x][y],[])+[B[X][Y]]
 except:1
def O(b,s,e,x,y,n=[],r=[]):
 if[]==s:yield e;return
 j,k=s[0]
 if len(p:={(J:=k-j*~y,X:=~j*~y+k),(K:=J+1,Y:=X+1),(J,K),(X,Y)}-{*r})>=b[j][k]:
  for i in combinations(p,b[j][k]):
   T=p-{*i}
   if all(~-(q in n)for q in T):
    E=eval(str(e))
    for A,B in T:E[A].remove(B);E[B].remove(A)
    if all(len(E[A])>1for A in E):yield from O(b,s[1:],E,x,y,n+[*i],r+[*T])
def f(x,y,d,t=' '):
 while 1:
  s=[0]*(x*y-(L:=int(x*y*d/20)))+[randint(1,3)for _ in R(L)];shuffle(s);b=[s[i:i+y]for i in R(0,len(s),y)];k=-1;B=[[(k:=k+1)for _ in R(y+1)]for _ in R(x+1)];D={}
  for Y in R(y+1):
   for X in R(x+1):U(D,B,X,Y,X,Y+1);U(D,B,X,Y,X+1,Y);U(D,B,X,Y+1,X,Y);U(D,B,X+1,Y,X,Y)
  for _ in O(b,[(X,Y)for X in R(x)for Y in R(y)if b[X][Y]],D,x,y):return'\n'.join([t.join(['+']*len(H))+'\n '+t.join([t,str(u)][u>0]for u in G)for H,G in zip(B,b)]+[t.join(['+']*len(B[0]))])
 
print(f(5,5,8))

ZnJvbSByYW5kb20gaW1wb3J0Kgpmcm9tIGl0ZXJ0b29scyBpbXBvcnQqClI9cmFuZ2UKZGVmIFUoRCxCLHgseSxYLFkpOgogdHJ5OkRbQlt4XVt5XV09RC5nZXQoQlt4XVt5XSxbXSkrW0JbWF1bWV1dCiBleGNlcHQ6MQpkZWYgTyhiLHMsZSx4LHksbj1bXSxyPVtdKToKIGlmW109PXM6eWllbGQgZTtyZXR1cm4KIGosaz1zWzBdCiBpZiBsZW4ocDo9eyhKOj1rLWoqfnksWDo9fmoqfnkrayksKEs6PUorMSxZOj1YKzEpLChKLEspLChYLFkpfS17KnJ9KT49YltqXVtrXToKICBmb3IgaSBpbiBjb21iaW5hdGlvbnMocCxiW2pdW2tdKToKICAgVD1wLXsqaX0KICAgaWYgYWxsKH4tKHEgaW4gbilmb3IgcSBpbiBUKToKICAgIEU9ZXZhbChzdHIoZSkpCiAgICBmb3IgQSxCIGluIFQ6RVtBXS5yZW1vdmUoQik7RVtCXS5yZW1vdmUoQSkKICAgIGlmIGFsbChsZW4oRVtBXSk+MWZvciBBIGluIEUpOnlpZWxkIGZyb20gTyhiLHNbMTpdLEUseCx5LG4rWyppXSxyK1sqVF0pCmRlZiBmKHgseSxkLHQ9JyAnKToKIHdoaWxlIDE6CiAgcz1bMF0qKHgqeS0oTDo9aW50KHgqeSpkLzIwKSkpK1tyYW5kaW50KDEsMylmb3IgXyBpbiBSKEwpXTtzaHVmZmxlKHMpO2I9W3NbaTppK3ldZm9yIGkgaW4gUigwLGxlbihzKSx5KV07az0tMTtCPVtbKGs6PWsrMSlmb3IgXyBpbiBSKHkrMSldZm9yIF8gaW4gUih4KzEpXTtEPXt9CiAgZm9yIFkgaW4gUih5KzEpOgogICBmb3IgWCBpbiBSKHgrMSk6VShELEIsWCxZLFgsWSsxKTtVKEQsQixYLFksWCsxLFkpO1UoRCxCLFgsWSsxLFgsWSk7VShELEIsWCsxLFksWCxZKQogIGZvciBfIGluIE8oYixbKFgsWSlmb3IgWCBpbiBSKHgpZm9yIFkgaW4gUih5KWlmIGJbWF1bWV1dLEQseCx5KTpyZXR1cm4nXG4nLmpvaW4oW3Quam9pbihbJysnXSpsZW4oSCkpKydcbiAnK3Quam9pbihbdCxzdHIodSldW3U+MF1mb3IgdSBpbiBHKWZvciBILEcgaW4gemlwKEIsYildK1t0LmpvaW4oWycrJ10qbGVuKEJbMF0pKV0pCiAgCnByaW50KGYoNSw1LDgpKQ==