「狂野飙车」は小 L が最も好きなゲームです。他のアマチュアプレイヤーとは異なり、小 L はゲームで遊ぶだけでなく、ゲームの設計を研究することにも長けているため、独特のゲーム戦略を持っています。

問題文

小 L は $n$ 回のゲームを行う予定です。各ゲームでは 1 枚のマップを使用し、小 L はそのマップでゲームを行う車を 1 台選びます。

小 L は、大文字の A、B、C で表される 3 台のレーシングカーを持っています。マップは小文字の x、a、b、c で表される 4 種類です。車 A はマップ a に、車 B はマップ b に、車 C はマップ c に適していません。一方、マップ x ではすべての車を使用できます。すべての車を使用できるマップは珍しく、多くても $d$ 枚です。

$n$ 回のゲームのマップは、小文字からなる文字列で表せます。例えば、S=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 からデータを読み込んでください。

1 行目には、2 つの非負整数 $n,d$ が与えられます。

2 行目には、文字列 $S$ が与えられます。

$n,d,S$ の意味は問題文のとおりです。$S$ は $n$ 文字からなり、そのうちちょうど $d$ 文字が小文字の x です。

3 行目には、車の使用に関する規則の数を表す正整数 $m$ が与えられます。続く $m$ 行には、それぞれ四つ組 $i,h_i,j,h_j$ が与えられます。$i,j$ は整数で、$h_i,h_j$ は文字 a、b、c のいずれかです。意味は問題文のとおりです。

出力

ファイル game.out に出力してください。

1 行出力してください。

解が存在しない場合は、-1 を出力してください（引用符は含めません）。

解が存在する場合は、大文字の A、B、C のみからなる長さ $n$ の文字列を出力してください。この文字列は、小 L が $n$ 回のゲームで使用する車を表します。解が複数ある場合は、いずれか 1 つを出力してください。

入出力例

入力 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 とすると、すべての条件を満たせないため、正しい答えとはみなされません。

小課題