题目背景
Problem Number: 24
在经过射命丸文的一番调教之后,琪露诺的智商总算增长了⑨点。
现在寺子屋又要开始考试了,琪露诺通过一些手段知道了答案中的一些信息,而且因为她冰雪聪明,她不希望自己的成绩进步太明显,从而被老师上白泽慧音特别关照。因此她找到了你寻求一些帮助。
(注意:考试作弊是不对的!)
题目描述
有 2⋅n 道选择题,每题有 A 和 B 两个选项。正确答案可以表示为一个长度为 2⋅n 的字符串。
现在你要构造出一份作答(长度同样为 2⋅n 的字符串),其中恰好有 a 个 A,同时与正确答案相比,你的作答恰好有 e 个错误。如果不存在这样的构造方案,报告无解。
注意:为了方便处理,本题保证 e≤n。
形式化地,给定 n,a,e 和一个长度为 2⋅n 的 01 串 s,你需要构造出一个恰好有 a 个字符是 0 的长度为 2⋅n 的 01 串 p,使得
(i=1∑2⋅n[si=pi])=e,
其中 [] 是 Iverson Bracket,详见「说明/提示」中的「提示」。
输入格式
本题含有多组数据。
第一行输入一个整数 T,表示数据组数。
对于每组数据:
- 第一行输入三个整数 n,a,e。
- 第二行输入一个长度为 2⋅n 的字符串,表示答案串。
输出格式
输出共 T 行。
对于每组数据:
- 若有解,输出一行一个长度为 2⋅n 的字符串,表示你构造的作答串。
- 若无解,输出一行一个字符串 -1。
提示
样例解释
对于数据 1,你构造出的作答串 BBAABB 中恰好有 2 个 A,与答案串相比刚好有 3 处不同(即,有 3 处错误):
ABABBABBAABB故符合要求。
对于数据 2,不存在合法构造方案。
数据规模与约定
对于 100% 的数据,有 1≤T≤100,1≤n≤105,0≤e≤n,0≤a≤2⋅n。
单组测试点内保证 ∑(2⋅n)≤106。
提示
A. Iverson Bracket
Iverson Bracket,是一种用方括号记号,如果方括号内的条件满足则为 1,不满足则为 0。更确切地讲,
[P]={1,0,If P is true,Otherwise.