「Who… who are you… really…?」

The girl smiled.

“—We are the Committee of Terminal Stagnation. A bunch of idiots who insist on guarding this world that has already ended!”

Problem Description

The rationalist Corporations — “money-laundering agencies”.

The bureaucratic Caus Academy — “bureaucrats”.

The meritocratic Azure Academy — “barbarians in white coats”.

…Although everyone argues like this all the time, there are still missions that must be carried out together.

Since such long names are impossible to remember— for your convenience as a contestant, we will refer to the three academies as A, B, and C.

There are $n$ students in total across the three academies. There are two types of missions, with $m_1$ and $m_2$ missions respectively. For each mission, two participants $a_i, b_i$ are specified.

• For all missions: if both participants are from academy C, you gain $2$ points of profit.
• For missions of the second type only: if exactly one of the two participants is from academy C, you suffer a loss of $1$ point. If the two participants are from the same academy, you suffer a loss of $2$ points.

Now, the academies of some students have already been determined. You need to determine the academies of all remaining students to maximize the total net profit of all missions (i.e., total profit minus total loss). Note that profits and losses can be added together; for example, if in a second-type mission both students are from academy C, then the net profit gained is $2-2=0$.

However, this problem is a bit too easy, so we are given a positive integer $k$. Next, concatenate the letters corresponding to each student’s academy in order to obtain a string of length $n$ consisting only of the letters A, B, and C. Among all assignments that maximize the net profit, you must output the lexicographically smallest $k$ solutions. If the number of solutions is less than $k$, you should output all solutions.

Input Format

The first line contains four non-negative integers $n, m_1, m_2, k$.

The second line contains a string of length $n$ consisting of ABC?, representing each student’s academy in order. A ? means it has not been determined yet.

The next $m_1$ lines each contain two positive integers $a_i, b_i$, representing the two students participating in a mission of the first type.

The next $m_2$ lines each contain two positive integers $a_i, b_i$, representing the two students participating in a mission of the second type.

Output Format

The first line contains one integer, the maximum total net profit.

Next, let $c$ be the number of distinct assignments that achieve the maximum net profit. Output $\min(c, k)$ lines, each being a string of length $n consisting of `ABC`. The output on line $i$ should be the $i$-th smallest assignment in lexicographical order.

Example

Example Input 1

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

Example Output 1

4
ACBC
BCAC
CCCC

Example Input 2

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

Example Output 2

-4
BBABBA
BCACBC

Constraints

Let $m = m_1 + m_2$.

For all data: $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$.

• Subtask 1 (2 points): $m = 0$;
• Subtask 2 (7 points): $n \le 15$;
• Subtask 3 (8 points): $n \le 2 \times 10^4$, all missions are of the first type;
• Subtask 4 (9 points): $n \le 2 \times 10^4$, initially no student’s academy is predetermined;
• Subtask 5 (24 points): $n \le 2 \times 10^4$, all missions are of the second type;
• Subtask 6 (20 points): $n \le 2 \times 10^4$, $k=1$;
• Subtask 7 (18 points): $n \le 2 \times 10^4$;
• Subtask 8 (12 points): no special constraints.

This problem uses a Special Judge. If you output the correct maximum profit but incorrect assignments, you can still get $50%$ of the score for the corresponding subtasks. If you only want this $50%$ score, one method is: after outputting the maximum profit on the first line, output nothing else.

Epilogue

“So—”

This will become a prayercurse for you. I believe it without a doubt.

“—You just need to be yourself. You don’t have to become the protagonist of some light novel, either.”

He widened his eyes. From the corners of his eyes, large teardrops rolled down.

—“Crack.”

That was the sound of the tiny handgun in his palm shattering.