题目背景

「你们……到底是谁……？」 少女笑了。

「一一我们是终末停滞委员会。是一群执意守护这个已经终结的世界的，喜欢做蠢事的家伙！」

合理主义的 Corporations——「洗钱机构」。

官僚主义的卡乌斯学院——「官僚人员」。

成果主义的苍之学园——「白衣蛮族」。

……尽管大家总是这样争吵着，可还是有需要一起出任务的时候呢。

题目描述

考虑到这么长的名字谁记得住啦——为了身为选手的你方便起见，下面我们把三所学园称为 A、B、C。

三所学园共有 $n$ 名学生。任务共有两种，分别有 $m_1,m_2$ 个，对于每个任务，都指定了两名参与者 $a_i,b_i$。

• 对于所有任务：当两名参与者都来自学园 C 时，获得 $2$ 点收益。
• 仅对于第二种任务：如果两名参与者有恰好一名来自学园 C，则遭受 $1$ 点损失。若两名参与者来自同样的学园，则遭受 $2$ 点损失。

现在，某些学生入学的学园已经确定，你需要确定剩余的所有学生入学的学园，来最大化所有任务的总净收益（即，总收益减去总损失）。注意收益和损失可以叠加，例如如果完成第二种任务的两名学生都来自学园 C，则获得的净收益是 $2-2=0$。

然而，这个问题实在有些太简单了，因此我们给出正整数 $k$，接下来，把学生所属的学园对应的字母依次连接，得到一个长度为 $n$ 的仅包含 A、B、C 三种字母的字符串，你需要给出所有最大化净收益的方案中，字符串的字典序前 $k$ 小的方案。若方案数小于 $k$，则你需要给出所有方案。

输入格式

第一行包含四个非负整数 $n,m_1,m_2,k$。

第二行包含一个长度为 $n$ 的由 ABC? 组成的字符串，依次代表每名学生入学的学园。如果为 ? 则代表尚未确定。

接下来 $m_1$ 行，每行包含两个正整数 $a_i,b_i$，代表参与第一种任务的两名学生。

接下来 $m_2$ 行，每行包含两个正整数 $a_i,b_i$，代表参与第二种任务的两名学生。

输出格式

第一行包含一个整数，代表最大的总净收益。

接下来，设 $c$ 为达到最大净收益的不同方案数。输出 $\min(c,k)$ 行，每行为一个长度为 $n$ 的由 ABC 组成的字符串。其中第 $i$ 行的输出对应字典序第 $i$ 小的方案。

4 2 3 100
????
4 2
4 2
3 1
3 1
1 3

4
ACBC
BCAC
CCCC

6 2 8 2
B???B?
2 6
1 3
1 5
1 3
6 4
3 2
5 4
3 4
5 6
1 3

-4
BBABBA
BCACBC

提示

数据范围

记 $m=m_1+m_2$。

对于所有数据：$1 \le n \le 10^5$，$0 \le m \le 10^5$，$1 \le k \le 6 \times 10^5$，$\max(n,m) \times k \le 10^7$。

• 子任务 1（2 分）：$m = 0$；
• 子任务 2（7 分）：$n \le 15$；
• 子任务 3（8 分）：$n \le 2 \times 10^4$，所有的任务都是第一种任务；
• 子任务 4（9 分）：$n \le 2 \times 10^4$，初始时，没有任何学生入学的学园已经确定；
• 子任务 5（24 分）：$n \le 2 \times 10^4$，所有的任务都是第二种任务；
• 子任务 6（20 分）：$n \le 2 \times 10^4$，$k=1$；
• 子任务 7（18 分）：$n \le 2 \times 10^4$；
• 子任务 8（12 分）：无特殊限制。

本题有 Special Judge，如果输出正确的最大收益和错误的方案，也可以获得对应子任务 $50\%$ 的分数。如果你只希望获得这 $50\%$ 的分数，一种方法是在第一行输出最大收益之后，后续不再输出其它内容。

后记

「所以啊——」

这会成为对你的 $\mathrm{\stackrel{诅咒}{祈愿}}$。我深信不疑。

「——你只要做你自己就好。不去当什么轻小说的主角，也可以哦。」

他瞪大了眼睛。从他的眼角，大颗的泪珠滚落而下。

——「啪咔」。

那是他手掌中，小小的手枪碎裂的声音。