aho corasick and dp

int l,r,k,n,m;int sz;int ending[1005];int to[1005][50],link[1005];string ss[1005],str;int dp[1005][1005],vis[1005][1005];

void Insert(string s,int indx){

    int curr = 0;
    int len = s.length();
    for(int i = 0;i<len;i++){

        int id = s[i] - 97;
        if(!to[curr][id])to[curr][id] = ++sz;
        curr = to[curr][id];

    }
    ending[curr]++;
    ///cout<<curr<<" lklklkl "<<endl;
}


void failure()
{
    int curr = 0;
    link[curr] = -1;
    queue<int>q;
    q.push(curr);
    while(!q.empty()){

        int x = q.front();
        q.pop();
        for(int i = 0;i<26;i++){

            if(!to[x][i])continue;
            if(!x)link[to[x][i]] = 0;
            else {
                int y = x;
                while(link[y]!=-1){

                    if(to[link[y]][i]){

                        link[to[x][i]] = to[link[y]][i];
                        break;
                    }
                    y = link[y];
                }
                if(link[y]==-1)link[to[x][i]] = 0;
            }
            ending[to[x][i]]+=ending[link[to[x][i]]];
            q.push(to[x][i]);

        }
    }
}

void CLEAR()
{
    for(int i = 0;i<1005;i++){

        for(int j = 0;j<1005;j++){

            dp[i][j] = -1;to[i][j] =  vis[i][j] = 0;
        }
        link[i] = ending[i] = 0;
    }
    sz = 0;
}

void print(int pos,int id)
{

    if(pos==n)return;
    int &ret = vis[pos][id];
    if(ret!=0)return ;
    ret = 1;
    int pk = str[pos] - 97;
    if(str[pos]=='?'){
        int mx = -1,ik,st;
        for(int i = 0;i<26;i++){

            int state = id;
            while(state!=-1&&to[state][i]==0)state = link[state];
            if(state==-1)state = 0;
            state = to[state][i];
            int x = dp[pos+1][state]+ending[state];
            if(x>mx){
                mx = x;
                ik = i;
                st = state;
            }
        }
        cout<<(char)(ik+'a');
        print(pos+1,st);
    }
    else {

        int state = id;
        while(state!=-1&&to[state][pk]==0)state = link[state];
        if(state==-1)state = 0;
        state = to[state][pk];
        cout<<str[pos];
        print(pos+1,state);
    }

}

int giveres(int pos,int id){
    if(pos==n)return 0;
    int &ret = dp[pos][id];
    if(ret!=-1)return ret;
    ret = 0;
    int pk = str[pos] - 'a';
    if(str[pos]=='?'){
        for(int i = 0;i<26;i++){

            int state = id;
            while(state!=-1&&to[state][i]==0)state = link[state];
            if(state==-1)state = 0;
            state = to[state][i];
            ret = max(ret,giveres(pos+1,state)+ending[state]);
        }
    }
    else {

        int state = id;
        while(state!=-1&&to[state][pk]==0)state = link[state];
        if(state==-1)state = 0;
        state = to[state][pk];
        ///cout<<ending[state].size()<<endl;
        ret = max(ret,giveres(pos+1,state)+ending[state]);
    }
    return ret;

}


int main()
{
    ///booster()
    ///read("input.txt");

    int t;
    cin>>t;
    while(t--){

        CLEAR();
        cin>>n>>m;
        cin>>str;
        for(int i = 0;i<m;i++){
            cin>>ss[i];
            Insert(ss[i],i);
        }
        failure();
        cout<<giveres(0,0)<<endl;
        for(int i = 0;i<1005;i++)for(int j = 0;j<1005;j++)if(dp[i][j]==-1)dp[i][j] = 0;
        print(0,0);
        cout<<endl;

    }