Description

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

Little L has three cars, denoted by uppercase letters $A$, $B$, and $C$. There are four types of maps, denoted by lowercase letters $x$, $a$, $b$, and $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 that are suitable for all cars are rare; there will be at most $d$ of them.

The maps for the $n$ games can be described by a string of lowercase letters. For example, $S=\texttt{xaabxcbc}$ means Little L plans to play $8$ games: the $1$-st and $5$-th maps are of type $x$, suitable for all cars; the $2$-nd and $3$-rd maps are of type $a$, unsuitable for car $A$; the $4$-th and $7$-th maps are of type $b$, unsuitable for car $B$; and the $6$-th and $8$-th maps are of type $c$, unsuitable for car $C$.

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

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

If there is no solution, output -1.

Input Format

The first line contains two non-negative integers, $n$ and $d$.

The second line contains a string $S$.

The meanings of $n$, $d$, and $S$ are as described above. The string $S$ contains $n$ characters, and exactly $d$ of them are the lowercase letter $x$.

The third line contains a positive integer $m$, indicating that there are $m$ car-usage rules.

The next $m$ lines each contain a quadruple $i, h_i, j, h_j$, where $i$ and $j$ are integers, and $h_i$ and $h_j$ are characters among $A$, $B$, and $C$, with meanings 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$ consisting only of uppercase letters $A$, $B$, and $C$, indicating how Little L arranges the cars for these $n$ games. If multiple solutions exist, output any one of them.

3 1
xcc
1
1 A 2 B

ABA

Hint

Sample 1 Explanation

Little $L$ plans to play $3$ games. The $1$-st map is of type $x$, suitable for all cars, and the $2$-nd and $3$-rd maps are of type $c$, unsuitable for car $C$.

Little $L$ requires: if car $A$ is used in game $1$, then car $B$ must be used in game $2$.

Assigning cars $A$, $B$, $A$ to the $3$ games satisfies all conditions.

Assigning cars $B B B$ or $B A A$ to the $3$ games also satisfies all conditions and is considered correct.

However, assigning cars $A A B$ or $A B C$ does not satisfy all conditions, so it is not considered correct.

Sample 2

See the attached file.

Constraints

Translated by ChatGPT 5