def crosswordPuzzle(crossword, words):
    # Write your code here
    solSteps=[]
    words = words.split(';')
    for i in range(len(crossword)):
       
        for j in range(len(crossword[i])):
            if crossword[i][j]=='-':
                if j<len(crossword[i])-1 and crossword[i][j+1]=='-' and (crossword[i][j-1]!='-' and j>0 ):
                    k=0
                    while crossword[i][j+k]=='-':
                       if j+k==9:
                           k+=1
                           break
                       k+=1
                    solSteps.append("h"+str(i)+str(j)+str(k))  
                elif j==0 and crossword[i][1]=='-':
                    k=0
                    while crossword[i][k]=='-':
                   
                       if k==9:
                           k=10
                           break
                       k+=1
                    solSteps.append("h"+str(i)+str(j)+str(k))
                elif  i<len(crossword)-1 and i> 0 and crossword[i+1][j]=='-' and crossword[i-1][j]!='-':
                    k=0
                    for x in range(i,len(crossword)):
                        if crossword[x][j]!='-':
                           break
                        k+=1
                    solSteps.append("v"+str(i)+str(j)+str(k))    
                elif  i== 0 and crossword[1][j]=='-':
                    k=0
                    for x in range(i,len(crossword)):
                        if crossword[x][j]!='-':
                           break
                        k+=1
                    solSteps.append("v"+str(i)+str(j)+str(k))    
    def canFillWord(word,blankword):
        orientation,row,col,size = blankword[0],blankword[1],blankword[2],blankword[3:]
        row,col,size = int(row),int(col),int(size)
        if len(word)!= size :
            return False
        if orientation=='v':
            for r in range(row, row+len(word)):
                if crossword[r][col]!="-" and crossword[r][col]!=word[r-row]:
                    return False
            for r in range(row, row+len(word)):
                if crossword[r][col]=="-" or crossword[r][col]==word[r-row]:
                    l=list(crossword[r])
                    l[col]=word[r-row]                
                    crossword[r]= "".join(l)
        if orientation=='h':
            for c in range(col, col+len(word)):
                if crossword[row][c]!="-" and crossword[row][c]!=word[c-col]:
                    return False
            l=list(crossword[row])
            for c in range(col,col+len(word)):
                if crossword[row][c]=="-" or crossword[row][c]==word[c-col]:
                    l[c] = word[c-col]
            crossword[row]="".join(l)
        return True    
    def unFill(word,blankword):
       
        orientation,row,col,size = blankword[0],int(blankword[1]),int(blankword[2]),int(blankword[3:])
        if orientation=='v':
            for r in range(row, row+len(word)):
                if crossword[r][col]==word[r-row]:
                    l=list(crossword[r])
                    l[col]="-"                
                    crossword[r]= "".join(l)
        if orientation=='h':
            l=list(crossword[row])
            for c in range(col,col+len(word)):
                if  crossword[row][c]==word[c-col]:
                    l[c] = "-"
            crossword[row]="".join(l)
           
    def solve(words,solSteps,i=0,k=0,done=[]):
        
        if len(done) == len(words):
            
            return crossword
       
        if canFillWord(words[i],solSteps[k]):
            
            if  words[i] not in done:
                if k < len(solSteps)-1:
                    k+=1
                done.append(words[i])
               
            
            i=0
           
            return solve(words,solSteps,i,k,done)
        else:
           
            if i < len(words)-1:
                i+=1
            else:
                i=0
               
                if done:
                    w = done[len(done)-1]
                    
                    for x in range(len(words)):
                        if len(words[x])==len(w) and words[x]!=w:
                            i = x
                            unFill(done[len(done)-1], solSteps[k-1])
                            
                            del done[len(done)-1]
                            if done:
                                
                                canFillWord(done[len(done)-1],solSteps[len(done)-1])
                            break
                    k = len(done)
                    print(words[i],solSteps[k])

                   
               
            return solve(words,solSteps,i,k,done)
    return solve(words,solSteps,i=0,k=0,done=[])

from collections import defaultdict
from copy import deepcopy


#
# Complete the 'crosswordPuzzle' function below.
#
# The function is expected to return a STRING_ARRAY.
# The function accepts following parameters:
#  1. STRING_ARRAY crossword
#  2. STRING words
#

def ishstart(crossword, i, j):
    if i == 9 or crossword[i + 1][j] == '+':
        return False
    if i == 0 or crossword[i - 1][j] == '+':
        return True
    return False


def isvstart(crossword, i, j):
    if j == 9 or crossword[i][j + 1] == '+':
        return False
    if j == 0 or crossword[i][j - 1] == '+':
        return True
    return False


def findend(crossword, i, j, wordtype):
    if wordtype == 'Horizontal':
        start = i
        while start < 10 and crossword[start][j] == '-':
            start += 1
        return (start - 1, j)
    if wordtype == 'Vertical':
        start = j
        while start < 10 and crossword[i][start] == '-':
            start += 1
        return (i, start - 1)


def findspots(crossword):
    spots = defaultdict(list)
    for i in range(10):
        for j in range(10):
            if crossword[i][j] == '-':
                if ishstart(crossword, i, j):
                    end = findend(crossword, i, j, 'Horizontal')
                    spots[end[0] - i + 1].append(((i, j), end))
                if isvstart(crossword, i, j):
                    end = findend(crossword, i, j, 'Vertical')
                    spots[end[1] - j + 1].append(((i, j), end))
    return spots


def putword(cs, spot, word):
    xi, yi = spot[0]
    xf, yf = spot[1]
    l = 0
    cross = deepcopy(cs)
    for i in range(xi, xf + 1):
        for j in range(yi, yf + 1):
            if cs[i][j] == '-' or cs[i][j] == word[l]:
                cross[i][j] = word[l]
                l += 1
            else:
                return False
    return cross


def match(words, spots, crossword):
    wlengths = defaultdict(list)
    for word in words:
        wlengths[len(word)].append(word)
    nwords = []
    for wlength, words in wlengths.items():
        nwords.append([len(words), wlength])
    nwords.sort()

    dp = None
    for nword in nwords:
        npossib, word_length = nword
        if npossib == 1:
            word_toput = wlengths[word_length][0]
            spot_toput = spots[word_length][0]
            if dp:
                crossword = dp[0]
            newcross = putword(crossword, spot_toput, word_toput)
            dp = [newcross]
        else:
            words_toput = wlengths[word_length]
            spots_toput = spots[word_length]
            sols = []
            if dp:
                for cross in dp:
                    poss = [cross]
                    for wd in words_toput:
                        newposs = []
                        for cross in poss:
                            for sp in spots_toput:
                                newcross = putword(cross, sp, wd)
                                if newcross:
                                    newposs.append(newcross)
                        poss = newposs
                        if not poss:
                            break
                    for sol in poss:
                        sols.append(sol)
            else:
                for wd in words_toput:
                    for sp in spots_toput:
                        newcross = putword(crossword, sp, wd)
                        if newcross:
                            sols.append(newcross)
            dp = sols

    return dp


def crosswordPuzzle(crossword, words):
    crossword = [list(el) for el in crossword]

    spots = findspots(crossword)
    # print(spots)
    words = words.split(';')'
		

    sol = match(words, spots, crossword)[-1][0]
    # pprint(sol)
    return [''.join(el) for el in sol]