「你们……到底是谁……？」

少女笑了。

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

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

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

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

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

题目描述

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

三所学园共有 $n$ 名学生。

任务共有两种，分别有 $m_1,m_2$ 个。每个任务都指定了两名参与者 $a_i,b_i$。

任务的收益与损失规则如下：

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

收益与损失可以叠加。例如，如果参与第二种任务的两名学生均来自学园 C，则该任务的净收益为 $2 - 2 = 0$。

现在，部分学生所属的学园已经确定。你需要确定其余所有学生所属的学园，使所有任务的总净收益最大。

接下来，将第 $1 \sim n$ 名学生所属学园对应的字母依次连接，得到一个长度为 $n$、仅包含 A、B、C 的字符串。

给定正整数 $k$，你需要输出所有使总净收益达到最大值的方案中，字典序最小的前 $k$ 个方案。如果最优方案数少于 $k$，则输出所有最优方案。

输入格式

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

第二行包含一个长度为 $n$、由字符 A、B、C、? 组成的字符串，依次表示每名学生所属的学园：

• A、B、C 表示该学生所属的学园已经确定；
• ? 表示该学生所属的学园尚未确定。

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

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

输出格式

第一行输出一个整数，表示最大的总净收益。

设达到最大净收益的不同方案数为 $c$。

接下来输出 $\min(c,k)$ 行，每行输出一个长度为 $n$、仅包含字符 A、B、C 的字符串。

第 $i$ 行应输出字典序第 $i$ 小的最优方案。

样例一

input

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

output

4
ACBC
BCAC
CCCC

样例二

input

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

output

-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$。

本题使用 Special Judge。

如果输出了正确的最大净收益，但输出的方案错误，仍可以获得对应子任务 $50\%$ 的分数。

如果只希望获得这 $50\%$ 的分数，可以仅在第一行输出最大净收益，随后不再输出其他内容。

后记

「所以啊——」

这会成为对你的祈愿诅咒。我深信不疑。

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

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

——「啪咔」。

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

时间限制：$\texttt{4s}$

空间限制：$\texttt{512MB}$