Asphalt เป็นเกมโปรดของ 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 รอบ แผนที่รอบที่ 1 และ 5 เป็นชนิด x ซึ่งเหมาะกับรถทุกคัน แผนที่รอบที่ 2 และ 3 เป็นชนิด a ซึ่งไม่เหมาะกับรถ A แผนที่รอบที่ 4 และ 7 เป็นชนิด b ซึ่งไม่เหมาะกับรถ B และแผนที่รอบที่ 6 และ 8 เป็นชนิด 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$ ตัว และมีอักษรตัวพิมพ์เล็ก x อยู่พอดี $d$ ตัว
บรรทัดที่สามเป็นจำนวนเต็มบวก $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 ต้องการว่า หากใช้รถ A ในรอบที่ 1 จะต้องใช้รถ B ในรอบที่ 2
ดังนั้นการจัดรถ A, B, A ให้ทั้ง 3 รอบตามลำดับจึงตรงตามเงื่อนไขทั้งหมด
หากจัดรถให้ทั้ง 3 รอบเป็น BBB หรือ BAA ตามลำดับ ก็ตรงตามเงื่อนไขทั้งหมดและถือเป็นคำตอบที่ถูกต้องเช่นกัน แต่หากจัดเป็น AAB หรือ ABC ตามลำดับ จะไม่ตรงตามเงื่อนไขทั้งหมด จึงไม่ถือเป็นคำตอบที่ถูกต้อง
งานย่อย
| หมายเลขกรณีทดสอบ | $n$ | $d$ | $m$ | คุณสมบัติอื่น |
|---|---|---|---|---|
| $1$ | $\le 2$ | $0$ | $\le 4$ | ไม่มี |
| $2$ | $\le 2$ | $\le n$ | $\le 4$ | ไม่มี |
| $3$ | $\le 5$ | $0$ | $\le 10$ | ไม่มี |
| $4$ | $\le 5$ | $\le n$ | $\le 10$ | ไม่มี |
| $5$ | $\le 10$ | $0$ | $\le 20$ | ไม่มี |
| $6$ | $\le 10$ | $\le 8$ | $\le 20$ | ไม่มี |
| $7$ | $\le 20$ | $0$ | $\le 40$ | $S$ มีเพียง c |
| $8$ | $\le 20$ | $0$ | $\le 40$ | ไม่มี |
| $9$ | $\le 20$ | $\le 8$ | $\le 40$ | $S$ มีเพียง x หรือ c |
| $10$ | $\le 20$ | $\le 8$ | $\le 40$ | ไม่มี |
| $11$ | $\le 100$ | $0$ | $\le 200$ | $S$ มีเพียง c |
| $12$ | $\le 100$ | $0$ | $\le 200$ | ไม่มี |
| $13$ | $\le 100$ | $\le 8$ | $\le 200$ | $S$ มีเพียง x หรือ c |
| $14$ | $\le 100$ | $\le 8$ | $\le 200$ | ไม่มี |
| $15$ | $\le 5000$ | $0$ | $\le 10\,000$ | ไม่มี |
| $16$ | $\le 5000$ | $\le 8$ | $\le 10\,000$ | $S$ มีเพียง x หรือ c |
| $17$ | $\le 5000$ | $\le 8$ | $\le 10\,000$ | ไม่มี |
| $18$ | $\le 50\,000$ | $0$ | $\le 100\,000$ | ไม่มี |
| $19$ | $\le 50\,000$ | $\le 8$ | $\le 100\,000$ | $S$ มีเพียง x หรือ c |
| $20$ | $\le 50\,000$ | $\le 8$ | $\le 100\,000$ | ไม่มี |