Background

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.

Title Description

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=\texttt{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 4-tuple ~(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.

Input Specification

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 Specification

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.

Sample Input 1

3 1
xcc
1
1 A 2 B

Sample Output 1

ABA

Explanation for Sample Output 1

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.

Sample Input / Output 2

See attached file for details.

Constraints

Test case	~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~ contains only ~c~
~8~	~\le 20~	~0~	~\le 40~	None
~9~	~\le 20~	~\le 8~	~\le 40~	~S~ contains only ~x~ or ~c~
~10~	~\le 20~	~\le 8~	~\le 40~	None
~11~	~\le 100~	~0~	~\le 200~	~S~ contains only ~c~
~12~	~\le 100~	~0~	~\le 200~	None
~13~	~\le 100~	~\le 8~	~\le 200~	~S~ contains only ~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~ contains only ~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~ contains only ~x~ or ~c~
~20~	~\le 5\times 10^4~	~\le 8~	~\le 10^5~	None