void removeH(vector<string>&crossword, int i, int j, vector<bool>& wePlaced) {
    for(int k=0;k<wePlaced.size();k++) {
        if(wePlaced[k]) crossword[i][j+k]='-';
    }
}
void removeV(vector<string>&crossword, int i, int j, vector<bool>& wePlaced) {
    for(int k=0;k<wePlaced.size();k++) {
        if(wePlaced[k]) crossword[i+k][j]='-';
    }
}

vector<bool> placeH(vector<string>&crossword, string currWord, int i, int j) {
    vector<bool> res;
    for(int k=0;k<currWord.length();k++) {
        if(crossword[i][j+k]=='-') {
            res.push_back(true);
            crossword[i][j+k] = currWord[k];
        }
        else res.push_back(false);
    }
    return res;
}
vector<bool> placeV(vector<string>&crossword, string currWord, int i, int j) {
    vector<bool> res;
    for(int k=0;k<currWord.length();k++) {
        if(crossword[i+k][j]=='-') {
            res.push_back(true);
            crossword[i+k][j] = currWord[k];
        }
        else res.push_back(false);
    }
    return res;
}

bool canPlaceH(vector<string>&crossword, string currWord, int i, int j) {
    
    int len = currWord.length();
    for(int x=0;x<len;x++) {
        if(x+j>=crossword.size()) return false;
        if(crossword[i][x+j]=='-' || crossword[i][x+j]==currWord[x]) continue;
        else return false;
    }
    return true;
}

bool canPlaceV(vector<string>&crossword, string currWord, int i, int j) {
    
    int len = currWord.length();
    for(int x=0;x<len;x++) {
        if(x+i>=crossword.size()) return false;
        if(crossword[x+i][j]=='-' || crossword[x+i][j]==currWord[x]) continue;
        else return false;
    }
    return true;
}
 
void solve(int indX, vector<string>&crossword, vector<string>words) {
    if(indX==words.size()) return;
    
    string currWord = words[indX];
    
    for(int i=0;i<crossword.size();i++) {
        for(int j=0;j<crossword.size();j++) {
            if(crossword[i][j]== '-' || crossword[i][j]==currWord[0]) {
                if(canPlaceH(crossword,currWord,i,j)) {
                    vector<bool> wePlaced = placeH(crossword,currWord,i,j);
                    solve(indX+1,crossword,words);
                    removeH(crossword,i,j, wePlaced);
                }
                if(canPlaceV(crossword, currWord, i, j)) {
                    vector<bool> wePlaced = placeV(crossword, currWord, i, j);
                    solve(indX+1,crossword,words);
                    removeV(crossword, i, j, wePlaced);
                }
            }
        }
    }
}

vector<string> crosswordPuzzle(vector<string>& crossword, string words) {
    vector<string>word;
    stringstream ss(words);
    while(ss.good()) {
        string substr;
        getline(ss, substr, ';');
        word.push_back(substr);
    }
    solve(0, crossword, word);
    return crossword;
}