#include <bits/stdc++.h>
using namespace std;

bool DB = false;
void GetInput(vector<int> &A, int t);

struct Animal
{    
    int type;
    int source;
    int dest;    
    
    Animal(){}
    Animal(int t, int s, int d) : type(t), source(s), dest(d) 
    {}
};


map<char, int> M = {{'E', 4}, {'D', 3}, {'C', 2}, {'M', 1}};
map<int, set<int>> invalid = {{1, {2,4}}, {2, {1,3}}, {3, {2,4}}, {4, {1,3}}}; 
map<int, int> C;
map<int, map<int, int>> S, D;

vector<int> animals = vector<int>(50000), source = vector<int>(50000), dest = vector<int>(50000), ans = vector<int>(50000);
//vector<int> ans;

int t, n, m;


void Solve(vector<Animal> A, vector<Animal> B, int i, int count)
{
    if(i > m) return;
    
    vector<Animal> next;
    map<int, int> c;
    
    int count_temp = count;
    
    for(auto animal : B)
    {
        int type = animal.type;
        int dest = animal.dest;
        
        if(dest == i)
        {
            count++;
        }
        else
        {
            next.push_back(animal);
            c[type]++;
        }
    }    
    B = next;
    //if(ans[count] == -1) ans[count] = i;
    ans[count] = (ans[count] == -1) ? i : min(ans[count], i);
        
    
    vector<Animal> temp = B;        
    map<int, int> c_temp = c;
    
    for(auto animal : A)
    {
        int type = animal.type;
        int source = animal.source;
        
        if(source == i)
        {
            bool valid_a = true, valid_b = true;
            
            for(auto other : invalid[type])
            {
                if(c[other] > 0)
                {
                    valid_a = false;
                    //break;
                }     
                if(c_temp[other] > 0)
                {
                    valid_b = false;
                }
            }
            if(!valid_a) continue;
            
            B.push_back(animal);
            Solve(A, B, i+1, count);
            
            if(valid_b)
            {
                temp.push_back(animal);
                c_temp[type]++;
                Solve(A, temp, i+1, count);                   
            }                        
            if(temp.size() > B.size())
            {
                //Solve(A, temp, i+1, count);   
            }
            B.pop_back();            
        }
    }
    Solve(A, B, i+1, count);
    Solve(A, temp, i+1, count);
}


int main() 
{
    cin >> t;
    
    if(t == 0)
    {
        DB = true;
        
        cin >> t;
    }
    
    while(t--)
    {
        cin >> m >> n;
     
        //cerr << m << "\t" << n << endl;
        
        fill(ans.begin(), ans.end(), -1);
        C.clear();
        S.clear();
        D.clear();
        
        GetInput(animals, 0);
        GetInput(source, 1);
        GetInput(dest, 2);
        
        vector<Animal> A;
        
        for(int i=0; i<n; i++)
        {
            Animal a = Animal(animals[i], source[i], dest[i]);
            A.push_back(a);
        }
        
        map<int, int> c = {{1, 0}, {2, 0}, {3, 0}, {4, 0}};         
        
        Solve(A, {}, 1, 0);
        
        for(int i=1; i<=n; i++)
        {
            cout << ans[i] << ' ';
        }
        cout << endl;
    }
    return 0;
}

void GetInput(vector<int> &A, int t)
{
    for(int i=0; i<n; i++)
    {
        if(t == 0)
        {
            char c;
            cin >> c;
            
            A[i] = M[c];
            C[A[i]]++;
        }
        else if(t == 1)
        {                    
            cin >> A[i]; 
            S[A[i]][animals[i]]++;
        }
        else if(t == 2)
        {
            cin >> A[i];
            D[A[i]][animals[i]]++;
        }
    }   
    /*
    DB = true;
    if(DB)
    {
        if(t == 2)
        {
            for(int i=1; i<=m; i++)
            {
                cerr << i << endl;
                
                for(auto it : D[i])
                {
                    cerr << "\t" << it.first << " | " << it.second << endl;    
                }
                
            }
        }
    }
    DB = false;
    */
}