Car Selection for Racing Games

Little L plans to play \(n\) racing games. In each game, a map is used and one car is chosen among three candidates: \(A\), \(B\), and \(C\). The maps come in four types: \(x\), \(a\), \(b\), and \(c\). On a map of type \(x\) all cars can be used; however, on map \(a\), car \(A\) cannot be used, on map \(b\) car \(B\) is unsuitable, and on map \(c\) car \(C\) is unsuitable. Moreover, maps of type \(x\) are rare, and there will be at most \(d\) such maps.

Additionally, there are special constraints given by quadruples \((i, h_i, j, h_j)\), meaning that if in game \(i\) car \(h_i\) is chosen, then in game \(j\) car \(h_j\) must be used. Your task is to determine a valid car selection for each game satisfying the above conditions. If more than one solution exists, output any one; if no solution exists, output \(-1\).

inputFormat

The first line contains two integers \(n\) and \(d\) representing the number of games and the maximum allowed number of maps of type \(x\) respectively.
The second line contains a string \(S\) of length \(n\) that describes the type of map used in each game. Each character is one of \(x\), \(a\), \(b\), or \(c\).
The third line contains an integer \(q\) which denotes the number of special constraints.
Each of the following \(q\) lines contains a quadruple \(i\, h_i\, j\, h_j\) (\(i\) and \(j\) are 1-indexed) that describes one constraint.

outputFormat

If there exists a valid car selection, output a string of length \(n\) where the \(i\)-th character represents the chosen car (either \(A\), \(B\), or \(C\)) for game \(i\). Otherwise, output \(-1\).

sample

8 2
xaabxcbc
2
2 B 4 C
3 C 7 A

ABCCAAAB