Game

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

Little L has three racing cars, $A$, $B$, and $C$. There are four map types, $x$, $a$, $b$, and $c$. Car $A$ is not suitable for map $a$, car $B$ is not suitable for map $b$, and car $C$ is not suitable for map $c$. Map $x$ is suitable for every car.

Maps that suit all racers are scarce. There are at most $d$ of them.

The games are described by a string of lowercase letters. For example, xaabxcbc describes 8 games. Games 1 and 5 use map $x$, which suits every car. Games 2 and 3 use map $a$, which is not suitable for car $A$. Games 4 and 7 use map $b$, which is not suitable for car $B$. Games 6 and 8 use map $c$, which is not suitable for car $C$.

Little L has some special requirements. Each requirement is a quadruple $(i, h_i, j, h_j)$, which means that if car $h_i$ is used in game $i$, then car $h_j$ must be used in game $j$.

Can you help Little L choose a car for each game? If several assignments work, print any one of them. If none exists, print -1.

The first line contains two integers $n$ and $d$.

The second line contains the string $S$ of length $n$. Exactly $d$ of its characters are $x$.

The third line contains an integer $m$, the number of requirements.

Each of the next $m$ lines contains $i$, $h_i$, $j$, and $h_j$, where $i$ and $j$ are integers and $h_i$ and $h_j$ are each one of $A$, $B$, or $C$.

Print one line. If no valid assignment exists, print -1. Otherwise, print a string of length $n$ made only of the capital letters $A$, $B$, and $C$, where the $k$-th character is the car used in game $k$.

$1 \le n \le 5\times 10^4$

$0 \le d \le \min(n, 8)$

$1 \le m \le 10^5$