狂野飙车 adalah permainan favorit Xiao L. Berbeda dari pemain amatir lainnya, selain bermain, Xiao L juga mahir meneliti rancangan permainan. Karena itu, ia memiliki strategi bermain yang berbeda dari orang lain.

Deskripsi Soal

Xiao L berencana memainkan $n$ permainan. Setiap permainan menggunakan sebuah peta, dan Xiao L memilih sebuah mobil untuk menyelesaikan permainan pada peta tersebut.

Xiao L memiliki tiga mobil balap, yang masing-masing dinyatakan dengan huruf kapital A, B, dan C. Terdapat empat jenis peta, yang masing-masing dinyatakan dengan huruf kecil x, a, b, dan c. Mobil A tidak cocok digunakan pada peta a, mobil B tidak cocok pada peta b, dan mobil C tidak cocok pada peta c, sedangkan peta x cocok untuk semua mobil. Peta yang cocok untuk semua mobil jarang ditemukan: jumlahnya paling banyak $d$.

Peta untuk $n$ permainan dapat dideskripsikan dengan sebuah string huruf kecil. Misalnya, S=xaabxcbc menyatakan bahwa Xiao L berencana memainkan 8 permainan. Peta permainan pertama dan kelima berjenis x, cocok untuk semua mobil; peta permainan kedua dan ketiga adalah a, tidak cocok untuk mobil A; peta permainan keempat dan ketujuh adalah b, tidak cocok untuk mobil B; peta permainan keenam dan kedelapan adalah c, tidak cocok untuk mobil C.

Xiao L memiliki beberapa persyaratan khusus untuk permainan, yang dapat dideskripsikan dengan kuadruple $(i,h_i,j,h_j)$. Artinya, jika mobil bertipe $h_i$ digunakan pada permainan ke-$i$, mobil bertipe $h_j$ harus digunakan pada permainan ke-$j$.

Dapatkah kamu membantu Xiao L memilih mobil untuk setiap permainan? Jika terdapat beberapa pengaturan, keluarkan salah satunya. Jika tidak ada solusi, keluarkan -1 (tanpa tanda kutip).

Masukan

Baca data dari berkas game.in.

Baris pertama masukan berisi dua bilangan bulat nonnegatif $n,d$.

Baris kedua masukan adalah sebuah string $S$.

Arti $n,d,S$ seperti yang dijelaskan dalam deskripsi soal. $S$ terdiri dari $n$ karakter dan tepat $d$ di antaranya merupakan huruf kecil x.

Baris ketiga masukan berisi sebuah bilangan bulat positif $m$, yang menyatakan banyaknya aturan penggunaan mobil. Berikutnya terdapat $m$ baris, masing-masing berisi kuadruple $i,h_i,j,h_j$, dengan $i,j$ berupa bilangan bulat dan $h_i,h_j$ berupa karakter a, b, atau c. Artinya seperti yang dijelaskan dalam deskripsi soal.

Keluaran

Tulis keluaran ke berkas game.out.

Keluarkan satu baris.

Jika tidak ada solusi, keluarkan -1 (tanpa tanda kutip).

Jika terdapat solusi, baris tersebut berisi sebuah string sepanjang $n$ yang hanya memuat huruf kapital A, B, dan C, yang menyatakan pengaturan mobil Xiao L untuk $n$ permainan tersebut. Jika terdapat beberapa solusi, keluarkan salah satunya.

Contoh

Masukan 1

3 1
xcc
1
1 A 2 B

Keluaran 1

ABA

Contoh 2

Lihat game/game2.in dan game/game2.ans di direktori peserta.

Penjelasan Contoh 1

Xiao L berencana memainkan 3 permainan. Peta permainan pertama berjenis x dan cocok untuk semua mobil, sedangkan peta permainan kedua dan ketiga adalah c dan tidak cocok untuk mobil C.

Xiao L menginginkan: jika permainan pertama menggunakan mobil A, permainan kedua harus menggunakan mobil B.

Maka, menetapkan mobil A, B, dan A untuk ketiga permainan secara berurutan memenuhi semua kondisi.

Pengaturan mobil berurutan BBB atau BAA juga memenuhi semua kondisi dan dianggap sebagai jawaban benar. Namun, pengaturan AAB atau ABC tidak memenuhi semua kondisi, sehingga tidak dianggap sebagai jawaban benar.

Subtugas