火柴网格构造

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

有一个 $2\times n$ 网格，每个格子填 A 或 B。第一行字符串 $s$ 已给定，请构造第二行，使所有上下或左右相邻、且字符不同的格子对数量恰为 $k$。

若不存在合法第二行，输出不可能；若存在，输出任意一个合法方案。

输入格式

第一行一个整数 $T$。

每组数据第一行两个整数 $n,k$，下一行一个长度为 $n$、仅含 A 和 B 的字符串 $s$。

输出格式

每组数据若无解，输出一行 NO。

否则先输出一行 YES，再输出一行长度为 $n$ 的合法第二行字符串。

样例输入 1

4
10 1
ABBAAABBAA
4 5
AAAA
9 17
BAAABBAAB
4 9
ABAB

样例输出 1

NO
YES
BABB
YES
ABABAABAB
NO

数据范围

$1\le T\le1000$，$1\le n\le2\times10^5$，$0\le k\le3n$，所有数据中 $\sum n\le2\times10^5$。

每个测试点独立计分。