| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 1 | 0 | 0 | 0.000% |
Asphalt is Little L's favorite game. Different from other amateur players, Little L is good at studying game design while playing games, so he has a unique game strategy.
Little L plans to play $n$ games, each game uses a map, and Little L will choose a car to complete the game on this map.
Little L has three racing cars, represented by capital letters $A,ドル $B,ドル and $C$. There are four types of maps, represented by lowercase letters $x,ドル $a,ドル $b,ドル and $c$.
Among them, car $A$ is not suitable for use on map $a,ドル car $B$ is not suitable for use on map $b,ドル car $C$ is not suitable for use on map $c,ドル and map $x$ is suitable for all cars to participate in.
There aren't many maps available for all racers, only $d$ maps at most.
$n$ The map of the game can be described by a string composed of lowercase letters. For example: $S=xaabxcbc$ means that little L plans to play 8ドル$ games, in which the map type of the 1ドル$ and 5ドル$ games is $x,ドル suitable for all racing cars, the 2ドル$ and 3ドル$ maps are $a,ドル not suitable for racing cars $A,ドル and the 4ドル$ and 7ドル$ games are $b,ドル not suitable for racing cars $B ,ドル 6ドル$ and 8ドル$ maps are $c,ドル not suitable for racing $C$.
Little L has some special requirements for the game. These requirements can be described by the quaternion $(i, h_i, j, h_j),ドル which means that if the car with the model $h_i$ is used in the $i$ game, then the car with the model $h_j$ should be used in the $j$ game.
Can you help little L choose the car to use for each game? If there are multiple schemes, output any one of them.
If there is no solution, output -1.
The first line of input contains two non-negative integers $n,ドル $d$.
Enter the second line as a string $S$.
The meanings of $n,ドル $d,ドル $S$ are described in the title, where $S$ contains $n$ characters, and exactly $d$ of them are lowercase letters $x$.
Enter a positive integer $m$ in the third line, indicating that there are $m$ car rules.
The next $m$ lines, each line contains a quaternion $i,h_i,j,h_j$ , where $i,j$ are integers, and $h_i,h_j$ are characters $A$ , $B$ or $C,ドル see the title description for the meaning.
Output one line.
Output -1 if there is no solution.
If there is a solution, it contains a string of length $n$ containing only capital letters A, B, and C, indicating how the little L arranges the use of the car in this $n$ game. If there are multiple sets of solutions, just output any one of them.
3 1 xcc 1 1 A 2 B
ABA
Little $L$ plans to play 3ドル$ games, where 1ドル$ map type is $x,ドル which is suitable for all cars, and 2ドル$ and 3ドル$ maps are $c,ドル which is not suitable for car racing $C$.
Little $L$ Wish: If 1ドル$ game uses car $A,ドル then 2ドル$ game uses car $B$.
Then arranging cars $A,ドル $B,ドル $A$ for the 3ドル$ games respectively would satisfy all the conditions.
All conditions are also met and considered correct if the car is assigned $BBB$ or $BAA$ for 3ドル$ games in turn.
However, when the car is arranged sequentially as $AAB$ or $ABC,ドル it is not considered the correct answer because all conditions cannot be met.