#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
using namespace std;


struct v{
    string str;
    int idx;
    vector<int> sep;
};


vector<v> list[2000];
map<string,string> gsb;
map<string,int> vv;
int n;

int common(string a, string b,int st){
    int sa=a.size();
    int sb=b.size();
    if(sa - st> sb -1 ){
        st = sa - sb + 1;
    }
    for(int i=st,t = sa - st;i<sa;i++,t--){
        bool is_match=true;
        for(int j=i,k=0;j<sa;j++,k++){
            if(a[j] != b[k]){
                is_match=false;
                break;
            }
        }
        if(is_match){
            return t;
        }
    }
    return 0;
}

string reduce_gsb(string a){
    while(true){
        bool found=false;
        int n=a.size();
        for(int i=0;i<n;i++){
            for(int j=i;j<n;j++){
                int len = j- i + 1;
                if(gsb.count(a.substr(i,len))){
                    string t = a.substr(0,i) + gsb[a.substr(i,len)] + a.substr(j+1,n - j);
                    a=t;
                    found=true;
                    break;
                }
            }
            if(found)break;
        }
        if(!found){
            break;
        }
    }
    return a;
}
string result="";
void divide(int n,vector<string> parts,int pos,string res_left,string res_right,int sign);
void mult(int n,vector<string> parts,string res_left,string res_right,int sign,int exception){

    int sg = 1;
    vector<string> tmp=parts;
    tmp.erase(tmp.begin());
    divide(n,tmp,0,res_left+parts[0],res_right,sign * sg);
    sg *= -1;
    int n_part= parts.size();
    for(int i=0;i<n_part - 1 ;i++){
        if(i == exception){
            sg *= -1;
            continue;
        }
        string g = parts[i] + parts[i+1];
        g = reduce_gsb(g);
        tmp = parts;
        tmp.erase(tmp.begin()+i);
        tmp.erase(tmp.begin()+i);
        tmp.insert(tmp.begin()+i,g);
        divide(n,tmp,i,res_left,res_right,sign* sg);
        sg *= -1;
    }
    tmp = parts;
    tmp.pop_back();
    divide(n,tmp,n_part-2,res_left, parts[n_part-1] + res_right ,sign* sg);
    sg *= -1;
}

void divide(int n,vector<string> parts,int pos,string res_left,string res_right,int sign){
    string str="";
    for(int i=0;i<parts.size();i++){
        str += parts[i];
    }
    int sg ;
    if(pos % 2 == 0)sg = 1;
    else sg = -1;
    if(vv.count(str) && vv[str] == n-1){
        if(sign == -1){
            result += "-";
        } else{
            result += "+";
        }
        result += res_left+"["+str+"]"+res_right;
        return;
    }
    int ln = parts[pos].length();
    str = "";
    for(int i=0;i<pos;i++){
        str += parts[i];
    }
    bool found=false;
    for(int i=1;i<ln;i++){
        string tmp=str + parts[pos].substr(0,i);

        if(vv.count(tmp) && vv[tmp] == pos){
            tmp = parts[pos].substr(i,ln -i);
            parts[pos]=  parts[pos].substr(0,i);
            parts.insert(parts.begin()+  pos+1,tmp);
            found=true;
            break;
        }
    }
    if(found){
        mult(n,parts,res_left,res_right,sign * sg,pos);
    }
}
int N;
int main(){
    cout<<"Enter N:"<<endl;
    cin>>N;
    cout<<"Enter number of elements of X"<<endl;
    cin>>n;
    cout<<"Enter elements of X space-separated"<<endl;
    for(int i=0;i<n;i++){
        v h;
        cin>>h.str;
        h.idx = 0;
        list[0].push_back(h);
        vv[h.str]= 0;
    }
    cout<<"Enter number of elements in GSB"<<endl;
    cin>>n;
    cout<<"Enter elements of GSB, in each line one element having two space-separated strings"<<endl;
    for(int i=0;i<n;i++){
        string a,b;
        cin>>a>>b;
        if(b=="1")b="";
        gsb[a]=b;
        v h;
        h.str = a;
        h.sep.push_back(0);
        h.idx = 1;
        list[1].push_back(h);
        vv[h.str] = 1;
    }
    for(int i=1;i<N;i++){
        for(int j =0;j<list[i].size();j++){
            for(int k=0;k<list[1].size();k++){
                int h= common(list[i][j].str,list[1][k].str,list[i][j].sep.back()+1);
                if(h ==0)continue;
                v u= list[i][j];
                u.idx += 1;
                u.sep.push_back(u.str.size()-1);
                int sb =list[1][k].str.size();
                u.str += list[1][k].str.substr(h,sb-h);
                list[i+1].push_back(u);
                vv[u.str] = u.idx;
            }
        }
    }
    cout<<"Elements of V"<<N<<" are: "<<endl;
    for(int j=0;j<list[N].size();j++){
        cout<<"V"<<N<<"["<<j<<"]: "<<list[N][j].str<<endl;
    }
    cout<<"Enter the index of element of you want to calculate its function"<<endl;
    int ind;
    cin>>ind;
    vector<string> parts;
    vector<int> sep = list[N][ind].sep;
    sep.insert(sep.begin(),-1);
    sep.push_back(list[N][ind].str.length() - 1);
    for(int i=0;i<sep.size() - 1;i++){
        int ln = sep[i+1]-sep[i];
        parts.push_back(list[N][ind].str.substr(sep[i]+1,ln));
    }
    mult(N,parts,"","",1,-1);
    cout<<"d["<<list[N][ind].str<<"]="<<result<<endl;
    cout<<"Enter ctrl + C to exit"<<endl;
    while(1);
}