«狂野飙车» — улюблена гра 小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 (без лапок).

Якщо розв'язок існує, рядок має містити лише великі літери $A$, $B$, $C$ і мати довжину $n$. Він описує, як 小L використовуватиме автомобілі в цих $n$ іграх. Якщо існує кілька розв'язків, виведіть будь-який із них.

Приклади

Вхідні дані 1

3 1
xcc
1
1 A 2 B

Вихідні дані 1

ABA

Приклад 2

Дивіться файли game/game2.in і game/game2.ans у каталозі учасника.

Пояснення до прикладу 1

小L планує зіграти 3 гри. У першій грі карта має тип $x$ і підходить для всіх автомобілів. У другій і третій іграх карти мають тип $c$ і не підходять для автомобіля $C$.

小L хоче, щоб у разі використання автомобіля $A$ у першій грі в другій грі використовувався автомобіль $B$.

Тоді вибір автомобілів $A$, $B$, $A$ відповідно для цих 3 ігор задовольняє всі умови.

Варіанти BBB і BAA для цих 3 ігор також задовольняють усі умови та вважаються правильними відповідями. А варіанти AAB і ABC не задовольняють усі умови, тому не вважаються правильними відповідями.

Підзадачі