Little L plans to play $n$ games, using one map for each game. For each game, Little L will choose one car to complete it.

Little L has three cars, denoted by the uppercase letters A, B, and C. There are four types of maps, denoted by the lowercase letters 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 all cars. Maps suitable for all cars are rare, with at most $d$ such maps.

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

Little L has some special requirements for the games, which can be described by quadruplets $(i, h_i, j, h_j)$, meaning 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 there are multiple solutions, output any one of them. If there is no solution, output "-1" (without quotes).

Input

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

The second line contains a string $S$.

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

The third line contains a positive integer $m$, representing $m$ car usage rules. The following $m$ lines each contain a quadruplet $i, h_i, j, h_j$, where $i, j$ are integers, and $h_i, h_j$ are characters 'a', 'b', or 'c'. The meanings are as described above.

Output

Output a single line.

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

If there is no solution, output "-1" (without quotes).

Examples

Input 1

3 1
xcc
1
1 A 2 B

Output 1

ABA

Note 1

Little L plans to play 3 games. The map type for the 1st game is x (suitable for all cars), and the maps for the 2nd and 3rd games are c (not suitable for car C).

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

Arranging cars A, B, A for these 3 games satisfies all conditions.

Arranging cars as BBB or BAA also satisfies all conditions and is considered a correct answer. However, arranging cars as AAB or ABC does not satisfy all conditions and is not considered a correct answer.

Examples 2

See game/game2.in and game/game2.ans in the contestant's directory.

Subtasks