#include int solve(int N, int A, int B, char s[], int a[], int b[]) { int i, j, k, l, x, y; static int sum[200003]; if (A == B) { for (i = 1; i <= A; i++) { a[i] = (N - A + i) * 2; b[i] = a[i]; if (s[i] == 'a') b[i]--; else a[i]--; } for (; i <= N; i++) { a[i] = (N - i + 1) * 2; b[i] = a[i]; if (s[i] == 'a') b[i]--; else a[i]--; } } else if (A > B) { if (B == 1) { for (i = 1, k = 0; i <= N; i++) if (s[i] == 'a') k++; if (k >= A) { for (i = 1, y = N * 2; s[i] == 'b'; i++) { b[i] = y--; a[i] = y--; } for (k = 0, x = y - A + 1, y = x - 1; i <= N; i++) { if (s[i] == 'b') { b[i] = y--; a[i] = y--; } else if (k == A) { a[i] = y--; b[i] = y--; } else { k++; a[i] = x++; b[i] = y--; } } } else if (N - k >= A) { for (i = 1, y = N * 2; s[i] == 'a'; i++) { a[i] = y--; b[i] = y--; } for (k = 1, x = 1; i <= N; i++) { if (s[i] == 'a') { a[i] = y--; b[i] = y--; } else if (k == A) { b[i] = y--; a[i] = y--; } else { k++; a[i] = x++; b[i] = y--; } } } else { for (i = N, sum[N+1] = 0; i >= 1; i--) { sum[i] = sum[i+1]; if (s[i] == 'a') sum[i]++; } for (i = 1, k = 0; i <= N; i++) { if (s[i] == 'b') { k++; if (s[i+1] != 'b' && k + sum[i] >= A) break; } } if (i > N) return 0; for (l = i, i = 1, x = 1, y = N * 2; i <= l; i++) { if (s[i] == 'a') { a[i] = y--; b[i] = y--; } else { a[i] = x++; b[i] = y--; } } for (x = y - (A - k) + 1, y = x - 1; i <= N; i++) { if (s[i] == 'b') { b[i] = y--; a[i] = y--; } else if (k == A) { a[i] = y--; b[i] = y--; } else { k++; a[i] = x++; b[i] = y--; } } } } else { for (i = 1, x = 1; B > 2; i++, A--, B--) { if (s[i] == 'a') { b[i] = x++; a[i] = x++; } else { a[i] = x++; b[i] = x++; } } for (l = i, k = 0, y = N * 2; i <= N; i++) { if (s[i] == 'a') k++; else b[i] = y--; } for (i = l, x += k - 1; i <= N; i++) if (s[i] == 'a') b[i] = x--; for (i = l, x += k + 1; i <= N; i++) { if (A > 1) { A--; a[i] = x++; } else if (A == 1) { A--; a[i] = y--; } else a[i] = y--; } for (i = l; i < N; i++) if (b[i] < b[i+1]) break; if (i == N) { for (i = l; i < N; i++) if (s[i] == s[i+1]) break; b[i] ^= b[i+1]; b[i+1] ^= b[i]; b[i] ^= b[i+1]; } } } else { if (A == 1) { for (i = 1, k = 0; i <= N; i++) if (s[i] == 'b') k++; if (k >= B) { for (i = 1, y = N * 2; s[i] == 'a'; i++) { a[i] = y--; b[i] = y--; } for (k = 0, x = y - B + 1, y = x - 1; i <= N; i++) { if (s[i] == 'a') { a[i] = y--; b[i] = y--; } else if (k == B) { b[i] = y--; a[i] = y--; } else { k++; b[i] = x++; a[i] = y--; } } } else if (N - k >= B) { for (i = 1, y = N * 2; s[i] == 'b'; i++) { b[i] = y--; a[i] = y--; } for (k = 1, x = 1; i <= N; i++) { if (s[i] == 'b') { b[i] = y--; a[i] = y--; } else if (k == B) { a[i] = y--; b[i] = y--; } else { k++; b[i] = x++; a[i] = y--; } } } else { for (i = N, sum[N+1] = 0; i >= 1; i--) { sum[i] = sum[i+1]; if (s[i] == 'b') sum[i]++; } for (i = 1, k = 0; i <= N; i++) { if (s[i] == 'a') { k++; if (s[i+1] != 'a' && k + sum[i] >= B) break; } } if (i > N) return 0; for (l = i, i = 1, x = 1, y = N * 2; i <= l; i++) { if (s[i] == 'b') { b[i] = y--; a[i] = y--; } else { b[i] = x++; a[i] = y--; } } for (x = y - (B - k) + 1, y = x - 1; i <= N; i++) { if (s[i] == 'a') { a[i] = y--; b[i] = y--; } else if (k == B) { b[i] = y--; a[i] = y--; } else { k++; b[i] = x++; a[i] = y--; } } } } else { for (i = 1, x = 1; A > 2; i++, A--, B--) { if (s[i] == 'b') { a[i] = x++; b[i] = x++; } else { b[i] = x++; a[i] = x++; } } for (l = i, k = 0, y = N * 2; i <= N; i++) { if (s[i] == 'b') k++; else a[i] = y--; } for (i = l, x += k - 1; i <= N; i++) if (s[i] == 'b') a[i] = x--; for (i = l, x += k + 1; i <= N; i++) { if (B > 1) { B--; b[i] = x++; } else if (B == 1) { B--; b[i] = y--; } else b[i] = y--; } for (i = l; i < N; i++) if (a[i] < a[i+1]) break; if (i == N) { for (i = l; i < N; i++) if (s[i] == s[i+1]) break; a[i] ^= a[i+1]; a[i+1] ^= a[i]; a[i] ^= a[i+1]; } } } return 1; } int judge(int N, int A, int B, char s[], int a[], int b[]) { int i; static int appear[400001]; for (i = 1; i <= N * 2; i++) appear[i] = 0; for (i = 1; i <= N; i++) { if (s[i] == 'a' && a[i] < b[i]) return 0; if (s[i] == 'b' && a[i] > b[i]) return 0; if (a[i] < 1 || a[i] > N * 2 || appear[a[i]] != 0) return 0; else appear[a[i]] = 1; if (b[i] < 1 || b[i] > N * 2 || appear[b[i]] != 0) return 0; else appear[b[i]] = 1; } int k, l, r, m; static int dp[200001]; for (i = 1, k = 0, dp[0] = 0; i <= N; i++) { l = 0; r = k; while (l < r) { m = (l + r + 1) / 2; if (dp[m] < a[i]) l = m; else r = m - 1; } dp[l+1] = a[i]; if (l == k) k++; } if (k != A) return 0; for (i = 1, k = 0, dp[0] = 0; i <= N; i++) { l = 0; r = k; while (l < r) { m = (l + r + 1) / 2; if (dp[m] < b[i]) l = m; else r = m - 1; } dp[l+1] = b[i]; if (l == k) k++; } if (k != B) return 0; return 1; } int DFS(int N, int A, int B, char s[], int a[], int b[], int k, int appear[]) { if (k > N) { if (judge(N, A, B, s, a, b) != 0) return 1; else return 0; } int i, j; for (i = 1; i <= N * 2; i++) { if (appear[i] != 0) continue; appear[i] = 1; for (j = i + 1; j <= N * 2; j++) { if (appear[j] != 0) continue; appear[j] = 1; if (s[k] == 'a') { a[k] = j; b[k] = i; } else { a[k] = i; b[k] = j; } if (DFS(N, A, B, s, a, b, k + 1, appear) != 0) return 1; appear[j] = 0; } appear[i] = 0; } return 0; } int naive(int N, int A, int B, char s[], int a[], int b[]) { int i; static int appear[400001]; for (i = 1; i <= N * 2; i++) appear[i] = 0; return DFS(N, A, B, s, a, b, 1, appear); } #define MT_N 624 #define MT_M 397 #define MT_MATRIX_A 0x9908b0dfUL #define MT_UPPER_MASK 0x80000000UL #define MT_LOWER_MASK 0x7fffffffUL static unsigned int mt[MT_N]; static int mti = MT_N + 1; void init_genrand(unsigned int s) { mt[0] = s & 0xffffffffUL; for (mti = 1; mti < MT_N; mti++) { mt[mti] = (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti); mt[mti] &= 0xffffffffUL; } } unsigned int genrand() { unsigned int y; static unsigned int mag01[2] = {0x0UL, MT_MATRIX_A}; if (mti >= MT_N) { int kk; if (mti == MT_N + 1) init_genrand(5489UL); for (kk = 0; kk < MT_N - MT_M; kk++) { y = (mt[kk] & MT_UPPER_MASK) | (mt[kk+1] & MT_LOWER_MASK); mt[kk] = mt[kk+MT_M] ^ (y >> 1) ^ mag01[y&0x1UL]; } for (; kk < MT_N - 1; kk++) { y = (mt[kk] & MT_UPPER_MASK) | (mt[kk+1] & MT_LOWER_MASK); mt[kk] = mt[kk+(MT_M-MT_N)] ^ (y >> 1) ^ mag01[y&0x1UL]; } y = (mt[MT_N-1] & MT_UPPER_MASK) | (mt[0] & MT_LOWER_MASK); mt[MT_N-1] = mt[MT_M-1] ^ (y >> 1) ^ mag01[y&0x1UL]; mti = 0; } y = mt[mti++]; y ^= (y >> 11); y ^= (y << 7) & 0x9d2c5680UL; y ^= (y << 15) & 0xefc60000UL; y ^= (y >> 18); return y; } int main() { int i, T, N, A, B, a[200001], b[200001]; char s[200003]; scanf("%d", &T); while (T--) { scanf("%d %d %d", &N, &A, &B); scanf("%s", &(s[1])); if (solve(N, A, B, s, a, b) == 0) printf("No\n"); else { printf("Yes\n"); for (i = 1; i <= N; i++) printf("%d ", a[i]); printf("\n"); for (i = 1; i <= N; i++) printf("%d ", b[i]); printf("\n"); } /* N = 5; A = genrand() % N + 1; B = genrand() % N + 1; for (i = 1, s[N+1] = 0; i <= N; i++) s[i] = 'a' + genrand() % 2; if (solve(N, A, B, s, a, b) != 0 && judge(N, A, B, s, a, b) == 0) { printf("%d %d %d\n", N, A, B); printf("%s\n", &(s[1])); for (i = 1; i <= N; i++) printf("%d ", a[i]); printf("\n"); for (i = 1; i <= N; i++) printf("%d ", b[i]); printf("\n"); } if (solve(N, A, B, s, a, b) == 0 && naive(N, A, B, s, a, b) != 0) { printf("%d %d %d\n", N, A, B); printf("%s\n", &(s[1])); for (i = 1; i <= N; i++) printf("%d ", a[i]); printf("\n"); for (i = 1; i <= N; i++) printf("%d ", b[i]); printf("\n"); } */ } fflush(stdout); return 0; }