狂野飆車是小 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。

說明

小 L 計劃進行 $3$ 場遊戲，其中第 $1$ 場的地圖類型是 x，適合所有賽車，第 $2$ 場和第 $3$ 場的地圖是 c，不適合賽車 C。

小 L 希望：若第 $1$ 場遊戲使用賽車 A，則第 $2$ 場遊戲使用賽車 B。

那麼為這 $3$ 場遊戲分別安排賽車 A、B、A 可以滿足所有條件。

若依次為 $3$ 場遊戲安排賽車為 BBB 或 BAA 時，也可以滿足所有條件，也被視為正確答案。但依次安排賽車為 AAB 或 ABC 時，因為不能滿足所有條件，所以不被視為正確答案。

子任務