لعبة 狂野飙车 هي اللعبة المفضلة لدى 小 L. وبخلاف اللاعبين الهواة الآخرين، فإن 小 L، إلى جانب لعبه، بارع أيضًا في دراسة تصميم اللعبة، ولذلك لديه استراتيجية لعب مميزة.

وصف المسألة

يخطط 小 L للعب $n$ جولة. تُستخدم في كل جولة خريطة واحدة، ويختار 小 L سيارة لإكمال الجولة على تلك الخريطة.

لدى 小 L ثلاث سيارات سباق، يرمز إليها بالأحرف الكبيرة A وB وC. وهناك أربعة أنواع من الخرائط، يرمز إليها بالأحرف الصغيرة x وa وb وc. السيارة A غير مناسبة للخريطة a، والسيارة B غير مناسبة للخريطة b، والسيارة C غير مناسبة للخريطة c، أما الخريطة x فمناسبة لجميع السيارات. والخرائط المناسبة لجميع السيارات نادرة، ولا يتجاوز عددها $d$.

يمكن وصف خرائط الجولات $n$ بسلسلة من الأحرف الصغيرة. فمثلًا، تعني S=xaabxcbc أن 小 L يخطط للعب 8 جولات: نوع خريطة الجولتين الأولى والخامسة هو x، وهو مناسب لجميع السيارات؛ ونوع خريطة الجولتين الثانية والثالثة هو a، وهو غير مناسب للسيارة A؛ ونوع خريطة الجولتين الرابعة والسابعة هو b، وهو غير مناسب للسيارة B؛ ونوع خريطة الجولتين السادسة والثامنة هو c، وهو غير مناسب للسيارة C.

لدى 小 L متطلبات خاصة للعبة، يمكن وصفها بالرباعية $(i,h_i,j,h_j)$: إذا استُخدمت السيارة من النوع $h_i$ في الجولة $i$، فيجب استخدام السيارة من النوع $h_j$ في الجولة $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 جولات: نوع خريطة الجولة الأولى هو x، وهو مناسب لجميع السيارات، ونوع خريطة الجولتين الثانية والثالثة هو c، وهو غير مناسب للسيارة C.

يريد 小 L أنه إذا استُخدمت السيارة A في الجولة الأولى، فإن السيارة B تُستخدم في الجولة الثانية.

وعليه، فإن اختيار السيارات A وB وA للجولات الثلاث على التوالي يحقق جميع الشروط.

كما أن اختيار السيارات بالترتيب BBB أو BAA للجولات الثلاث يحقق جميع الشروط، ويُعد إجابة صحيحة أيضًا. أما اختيار AAB أو ABC بالترتيب فلا يحقق جميع الشروط، ولذلك لا يُعد إجابة صحيحة.

المهام الفرعية