게임

Little L은 $n$개의 게임을 할 계획이다. 각 게임은 맵 하나에서 진행되며, Little L은 그 맵에서 게임을 완료할 차량을 고른다.

Little L에게는 A, B, C 세 종류의 레이싱 카가 있다. 맵은 x, a, b, c 네 종류가 있다. 차량 A는 맵 a에 적합하지 않고, 차량 B는 맵 b에 적합하지 않으며, 차량 C는 맵 c에 적합하지 않다. 맵 x는 모든 차량이 참가하기에 적합하다.

모든 레이서에게 맞는 맵은 많지 않아서, 그런 맵은 최대 $d$개뿐이다.

게임의 맵은 소문자로 이루어진 문자열로 나타낸다. 예를 들어 xaabxcbc는 8개의 게임을 뜻한다. 1번과 5번 게임의 맵은 x이므로 모든 차량에 적합하다. 2번과 3번 게임의 맵은 a이므로 차량 A에는 적합하지 않다. 4번과 7번 게임의 맵은 b이므로 차량 B에는 적합하지 않다. 6번과 8번 게임의 맵은 c이므로 차량 C에는 적합하지 않다.

Little L에게는 특별한 요구 조건이 있다. 각 조건은 $(i, h_i, j, h_j)$의 네 값으로 표현되며, $i$번 게임에서 차량 $h_i$를 사용하면 $j$번 게임에서는 차량 $h_j$를 사용해야 한다는 뜻이다.

각 게임에 사용할 차량을 골라 줄 수 있는가? 조건을 만족하는 방법이 여럿이면 그중 아무것이나 하나를 출력한다. 해가 없으면 -1을 출력한다.

첫 줄에 두 정수 $n$과 $d$가 주어진다.

둘째 줄에 길이 $n$인 문자열 $S$가 주어진다. $S$에 들어 있는 x는 정확히 $d$개이다.

셋째 줄에 조건의 개수 $m$이 주어진다.

이어지는 $m$개의 줄에는 각각 $i$, $h_i$, $j$, $h_j$가 주어진다. $i$와 $j$는 정수이고, $h_i$와 $h_j$는 각각 A, B, C 중 하나이다.

한 줄을 출력한다. 해가 없으면 -1을 출력한다. 해가 있으면 대문자 A, B, C로만 이루어진 길이 $n$의 문자열을 출력한다. $k$번째 문자는 $k$번째 게임에서 사용할 차량이다.

$1 \le n \le 5\times 10^4$

$0 \le d \le \min(n, 8)$

$1 \le m \le 10^5$