The Game

Problem Source

NOI2017

Problem Description

Little L plans to play $n$ games, each game using one map, and Little L will choose one car to complete the game on that map.

Little L has three cars, denoted by the uppercase letters $A$, $B$, $C$. There are four kinds of maps, denoted by the lowercase letters $x$, $a$, $b$, $c$.

Among them, car $A$ is not suitable for map $a$, car $B$ is not suitable for map $b$, car $C$ is not suitable for map $c$, while map $x$ is suitable for all cars.

Maps suitable for all cars are rare, and there are at most $d$ of them.

The $n$ games' maps can be described by a string of lowercase letters. For example, $S = \texttt{xaabxcbc}$ means Little L plans $8$ games, where the 1st and 5th games are on map $x$ (suitable for all cars), the 2nd and 3rd are on map $a$ (not suitable for car $A$), the 4th and 7th are on map $b$ (not suitable for car $B$), and the 6th and 8th are on map $c$ (not suitable for car $C$).

Little L has some special requirements for the games, which can be described by a quadruple $(i, h_i, j, h_j)$, meaning: if car $h_i$ is used in the $i$-th game, then car $h_j$ must be used in the $j$-th game.

Can you help Little L choose a car for each game? If there are multiple valid plans, output any one of them.

If there is no solution, output -1.

Input Format

The first line contains two non-negative integers $n\ (1 \le n \le 5 \times 10^4)$, $d\ (0 \le d \le 8)$.

The second line contains a string $S$.

The meanings of $n$, $d$, $S$ are as in the problem description; $S$ contains $n$ characters, exactly $d$ of which are the lowercase letter $x$.

The third line contains a positive integer $m\ (1 \le m \le 10^5)$, the number of car-usage rules.

The next $m$ lines each contain a quadruple $i, h_i, j, h_j$, where $i, j$ are integers and $h_i, h_j$ are characters among $A$, $B$, $C$, as described above.

Output Format

Output one line.

If there is no solution, output -1.

If there is a solution, output a string of length $n$ containing only the uppercase letters $A, B, C$, representing how Little L arranges the cars for the $n$ games. If multiple solutions exist, output any one of them.

Sample Input

3 1
xcc
1
1 A 2 B

Sample Output

ABA

Sample Explanation

Little L plans $3$ games; the 1st game is on map $x$ (suitable for all cars), and the 2nd and 3rd games are on map $c$ (not suitable for car $C$).

Little L wants: if car $A$ is used in the 1st game, then car $B$ must be used in the 2nd game.

Then assigning cars $A, B, A$ to the three games respectively satisfies all conditions.

Assigning $BBB$ or $BAA$ to the three games also satisfies all conditions and is also considered a correct answer.

But assigning $AAB$ or $ABC$ does not satisfy all conditions, so they are not considered correct answers.