狂野飙车係小 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 場遊戲，其中第 1 場同第 5 場嘅地圖類型係 x，適合所有賽車；第 2 場同第 3 場嘅地圖係 a，唔適合賽車 A；第 4 場同第 7 場嘅地圖係 b，唔適合賽車 B；第 6 場同第 8 場嘅地圖係 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$ 條用車規則。之後 $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。

說明 1

小 L 計劃玩 3 場遊戲，其中第 1 場嘅地圖類型係 x，適合所有賽車；第 2 場同第 3 場嘅地圖係 c，唔適合賽車 C。

小 L 希望：如果第 1 場遊戲用賽車 A，第 2 場遊戲就要用賽車 B。

咁樣，呢 3 場遊戲分別安排賽車 A、B、A，就可以滿足所有條件。

如果順序為 3 場遊戲安排賽車為 BBB 或 BAA，亦可以滿足所有條件，亦會視為正確答案。不過，如果順序安排賽車為 AAB 或 ABC，因為唔能夠滿足所有條件，所以唔會視為正確答案。

子任務