#include using namespace std; #define F first #define S second #define mp make_pair #define pb push_back #define MAXN 101010 #define INF 1000000000 typedef long long int ll; struct pt{ int x, id, tipo; pt(){} pt(int a, int b, int c){ x = a; id = b; tipo = c; } }; map > >, int> memo; int type[MAXN]; int origin[MAXN]; int destiny[MAXN]; vector comeca[MAXN]; vector termina[MAXN]; int n, m, MM; vector v; bool pode(int id, int E, int D, int C, int M){ id = type[id]; if(id == 0){ if(D > 0 || M > 0) return false; } if(id == 1){ if(E > 0 || C > 0) return false; } if(id == 2){ if(D > 0) return false; } if(id == 3){ if(C > 0 || E > 0) return false; } return true; } bool compara(pt &a, pt &b){ if(a.x == b.x) return a.tipo < b.tipo; return a.x < b.x; } int solve(int pos, set bag, int cnt, int E, int D, int C, int M){ if(pos == (int)v.size()) return INF; int ce=0, cd=0, cc=0, cm=0; int ans = INF; set nwBag; if(v[pos].tipo == 1){ if(pode(v[pos].id, E, D, C, M)){ nwBag = bag; nwBag.insert(v[pos].id); if(type[v[pos].id] == 0) ce = 1; if(type[v[pos].id] == 1) cd = 1; if(type[v[pos].id] == 2) cc = 1; if(type[v[pos].id] == 3) cm = 1; ans = min(solve(pos+1, bag, cnt, E, D, C, M), solve(pos+1, nwBag, cnt, E + ce, D + cd, C + cc, M + cm)); }else{ ans = solve(pos+1, bag, cnt, E, D, C, M); } }else{ if(bag.count(v[pos].id)){ if(cnt == MM-1) return v[pos].x; nwBag = bag; nwBag.erase(v[pos].id); if(type[v[pos].id] == 0) ce = -1; if(type[v[pos].id] == 1) cd = -1; if(type[v[pos].id] == 2) cc = -1; if(type[v[pos].id] == 3) cm = -1; ans = solve(pos+1, nwBag, cnt+1, E + ce, D + cd, C + cc, M + cm); }else{ ans = solve(pos+1, bag, cnt, E, D, C, M); } } return ans; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int tc; char c; cin >> tc; while (tc--) { cin >> n >> m; v.clear(); for (int i = 0; i < m; i++) { cin >> c; if(c=='E') type[i] = 0; if(c=='D') type[i] = 1; if(c=='C') type[i] = 2; if(c=='M') type[i] = 3; } for (int i = 0; i < m; i++) { cin >> origin[i]; v.pb(pt(origin[i], i, 1)); } for (int i = 0; i < m; i++) { cin >> destiny[i]; v.pb(pt(destiny[i], i, 0)); } sort(v.begin(), v.end(), compara); //~ for (int i = 0; i < (int)v.size(); i++) //~ { //~ cout << v[i].x << " " << v[i].id << " " << v[i].tipo << endl; //~ } set s; int ans; for (int i = 1; i <= m; i++) { MM = i; s.clear(); ans = solve(0, s, 0, 0, 0, 0, 0); if(ans >= INF) ans = -1; if(i > 1) cout << " "; cout << ans; } cout << "\n"; } return 0; }