狂野飙车 — любимая игра 小 L. В отличие от других любителей, 小 L не только играет, но и хорошо разбирается в устройстве игры, поэтому у него особая игровая стратегия.

Условие задачи

小 L планирует сыграть $n$ игр. В каждой игре используется одна карта, и 小 L выбирает автомобиль, на котором пройдёт эту карту.

У 小 L есть три гоночных автомобиля, обозначенные прописными буквами A, B, C. Существуют четыре вида карт, обозначенные строчными буквами x, a, b, c. Автомобиль A не подходит для карты a, автомобиль B не подходит для карты b, а автомобиль C не подходит для карты c. Карта x подходит для всех автомобилей. Карты, подходящие для всех автомобилей, встречаются редко: их будет не более $d$.

Карты для $n$ игр можно описать строкой из строчных букв. Например, $S=\texttt{xaabxcbc}$ означает, что 小 L планирует сыграть 8 игр. В первой и пятой играх карта имеет тип x и подходит для всех автомобилей; во второй и третьей — тип a, который не подходит для автомобиля A; в четвёртой и седьмой — тип b, который не подходит для автомобиля B; в шестой и восьмой — тип c, который не подходит для автомобиля C.

У 小 L есть особые требования к играм. Каждое из них описывается четвёркой $(i,h_i,j,h_j)$: если в $i$-й игре используется автомобиль модели $h_i$, то в $j$-й игре должен использоваться автомобиль модели $h_j$.

Помогите 小 L выбрать автомобиль для каждой игры. Если решений несколько, выведите любое. Если решения нет, выведите -1 без кавычек.

Входные данные

Данные считываются из файла game.in.

Первая строка содержит два неотрицательных целых числа $n,d$.

Вторая строка содержит строку $S$.

Значения $n,d,S$ описаны в условии задачи. Строка $S$ содержит $n$ символов, ровно $d$ из которых — строчная буква x.

Третья строка содержит положительное целое число $m$ — количество правил использования автомобилей. Каждая из следующих $m$ строк содержит четвёрку $i,h_i,j,h_j$, где $i,j$ — целые числа, а $h_i,h_j$ — символы a, b или c. Их смысл описан в условии задачи.

Выходные данные

Результат выводится в файл game.out.

Выведите одну строку.

Если решения нет, выведите -1 без кавычек.

Если решение существует, выведите строку длины $n$, состоящую только из прописных букв A, B, C и описывающую выбор автомобилей 小 L в этих $n$ играх. Если решений несколько, можно вывести любое из них.

Примеры

Входные данные 1

3 1
xcc
1
1 A 2 B

Выходные данные 1

ABA

Пример 2

См. файлы game/game2.in и game/game2.ans в каталоге участника.

Примечание

小 L планирует сыграть 3 игры. В первой игре карта имеет тип x и подходит для всех автомобилей, а во второй и третьей — тип c, который не подходит для автомобиля C.

小 L хочет, чтобы при использовании автомобиля A в первой игре во второй игре использовался автомобиль B.

Таким образом, выбор автомобилей A, B, A для этих трёх игр удовлетворяет всем условиям.

Выбор BBB или BAA для трёх последовательных игр также удовлетворяет всем условиям и считается правильным ответом. Однако выбор AAB или ABC не удовлетворяет всем условиям и не считается правильным ответом.

Подзадачи