P3825 [NOI2017] Game

[Original problem time limit: 1 s.] Asphalt is Little L’s favorite game. Unlike other casual players, Little L studies game design in his spare time, so he has a unique strategy for playing.

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`.

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 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.

### 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 | Test point ID | $n$ | $d$ | $m$ | Other properties | | :-----------: | :----------------: | :-----: | :--------: | :----------------------------: | | $1$ | $\le 2$ | $0$ | $\le 4$ | None | | $2$ | $\le 2$ | $\le n$ | $\le 4$ | None | | $3$ | $\le 5$ | $0$ | $\le 10$ | None | | $4$ | $\le 5$ | $\le n$ | $\le 10$ | None | | $5$ | $\le 10$ | $0$ | $\le 20$ | None | | $6$ | $\le 10$ | $\le 8$ | $\le 20$ | None | | $7$ | $\le 20$ | $0$ | $\le 40$ | $S$ only contains $c$ | | $8$ | $\le 20$ | $0$ | $\le 40$ | None | | $9$ | $\le 20$ | $\le 8$ | $\le 40$ | $S$ only contains $x$ or $c$ | | $10$ | $\le 20$ | $\le 8$ | $\le 40$ | None | | $11$ | $\le 100$ | $0$ | $\le 200$ | $S$ only contains $c$ | | $12$ | $\le 100$ | $0$ | $\le 200$ | None | | $13$ | $\le 100$ | $\le 8$ | $\le 200$ | $S$ only contains $x$ or $c$ | | $14$ | $\le 100$ | $\le 8$ | $\le 200$ | None | | $15$ | $\le 5\times 10^3$ | $0$ | $\le 10^4$ | None | | $16$ | $\le 5\times 10^3$ | $\le 8$ | $\le 10^4$ | $S$ only contains $x$ or $c$ | | $17$ | $\le 5\times 10^3$ | $\le 8$ | $\le 10^4$ | None | | $18$ | $\le 5\times 10^4$ | $0$ | $\le 10^5$ | None | | $19$ | $\le 5\times 10^4$ | $\le 8$ | $\le 10^5$ | $S$ only contains $x$ or $c$ | | $20$ | $\le 5\times 10^4$ | $\le 8$ | $\le 10^5$ | None | Translated by ChatGPT 5