#include #include #include #include using namespace std; struct node { int dest, vol; }; int p, h, w; const int src = 0; const int sink = 1; int _fng(char c) { if (c >= 'A' && c <= 'Z') return c-'A'; return 26; } #define MAXS 10000000 #define msg(x) (_fng(x)+2) #define pg1(x) (_fng(x)+28) #define pg2(x) (_fng(x)+55) #define ppg(a,x) (28 + (a)*27 + _fng(x)) int G[128][128]; char buff[MAXS]; int ds[128]; int ps[128]; int pr[128]; #define imin(a,b) ((a)<(b)?(a):(b)) int augment(void) { memset(ds, 0, sizeof(ds)); memset(ps, 0, sizeof(ps)); memset(pr, -1, sizeof(pr)); ds[src] = 999666111; while (1) { int bi, mdist=0; bi = -1; for (int i = 0; i < 128; i++) if (!ps[i] && ds[i] > mdist) { mdist = ds[i]; bi = i; } if (bi == -1) return 0; if (bi == sink) return ds[bi]; ps[bi] = 1; for (int i = 0; i < 128; i++) { if (!ps[i] && ds[i] < imin(ds[bi], G[bi][i])) { pr[i] = bi; ds[i] = imin(ds[bi], G[bi][i]); } } } } int flow(void) { int all = 0; int x; int cf; while (1) { cf = augment(); if (cf == 0) break; all += cf; x = sink; while (x != 0) { G[pr[x]][x] -= cf; G[x][pr[x]] += cf; x = pr[x]; } } return all; } int main(void) { int t; //freopen("c.in", "rt", stdin); scanf("%d", &t); while (t--) { //scanf("%d%d%d", &p, &h, &w); cin >> p >> h >> w; memset(G, 0, sizeof(G)); vector book; for (int pg = 0; pg < p; pg++) { for (int row = 0; row < h; row++) { string s; cin >> s; while (s.length() < w) s+=' '; book.push_back(s); } } if (pg % 2) { string s; for (int i = 0; i < w; i++) s += ' '; for (int i = 0; i < h; i++) book.push_back(s); } string m; cin >> m; int hist[26] = {0}; for (int i = 0; i < m.length(); i++) { G[src][msg(m[i])]++; hist[_fng(m[i])]++; } for (int pg = 0; pg < p; pg++) { for (int row = 0; row < h; row++) { for (int col = 0; col < w; col++) { char c1 = book[pg*h + row][col]; if (pg % 2 == 0) { char c2 = book[(pg+1)*h+row][w-1-col]; G[msg(c1)][pg1(c1)] ++; G[pg1(c1)][pg2(c2)] ++; G[msg(c2)][pg1(c1)] ++; } if (pg % 2 == 1) { G[pg2(c1)][sink] ++; } } } } int res = flow(); if (res < m.length()) printf("NO\n"); else printf("YES\n"); } return 0; }