狂野飙车 là trò chơi yêu thích nhất của Tiểu L. Khác với những người chơi nghiệp dư khác, ngoài việc chơi, Tiểu L còn giỏi nghiên cứu thiết kế trò chơi, vì thế cậu có chiến thuật chơi khác biệt.

Mô tả bài toán

Tiểu L dự định chơi $n$ ván, mỗi ván sử dụng một bản đồ. Tiểu L sẽ chọn một chiếc xe để hoàn thành ván chơi trên bản đồ đó.

Tiểu L có ba xe đua, lần lượt được ký hiệu bằng các chữ cái in hoa A, B, C. Có bốn loại bản đồ, lần lượt được ký hiệu bằng các chữ cái thường x, a, b, c. Xe A không thích hợp với bản đồ a, xe B không thích hợp với bản đồ b, xe C không thích hợp với bản đồ c, còn bản đồ x thích hợp với mọi xe. Bản đồ thích hợp với mọi xe khá hiếm, nhiều nhất chỉ có $d$ bản đồ.

Các bản đồ của $n$ ván chơi có thể được mô tả bằng một xâu chữ cái thường. Ví dụ, $S=\texttt{xaabxcbc}$ có nghĩa là Tiểu L dự định chơi 8 ván; bản đồ ở ván 1 và 5 có loại x, thích hợp với mọi xe; bản đồ ở ván 2 và 3 có loại a, không thích hợp với xe A; bản đồ ở ván 4 và 7 có loại b, không thích hợp với xe B; bản đồ ở ván 6 và 8 có loại c, không thích hợp với xe C.

Tiểu L có một số yêu cầu đặc biệt đối với trò chơi. Mỗi yêu cầu được mô tả bằng một bộ bốn $(i,h_i,j,h_j)$, có nghĩa là nếu dùng xe loại $h_i$ ở ván thứ $i$ thì phải dùng xe loại $h_j$ ở ván thứ $j$.

Bạn có thể giúp Tiểu L chọn xe cho mỗi ván không? Nếu có nhiều phương án, hãy in ra một phương án bất kỳ. Nếu không có lời giải, in ra -1 (không có dấu ngoặc kép).

Dữ liệu vào

Đọc dữ liệu từ tệp game.in.

Dòng đầu tiên chứa hai số nguyên không âm $n,d$.

Dòng thứ hai chứa một xâu $S$.

Ý nghĩa của $n,d,S$ được nêu trong phần mô tả bài toán; $S$ gồm $n$ ký tự, trong đó có đúng $d$ chữ cái thường x.

Dòng thứ ba chứa một số nguyên dương $m$, biểu thị có $m$ quy tắc sử dụng xe. Mỗi dòng trong $m$ dòng tiếp theo chứa một bộ bốn $i,h_i,j,h_j$, trong đó $i,j$ là số nguyên, $h_i,h_j$ là ký tự a, b hoặc c; ý nghĩa được nêu trong phần mô tả bài toán.

Dữ liệu ra

Ghi kết quả vào tệp game.out.

In ra một dòng.

Nếu không có lời giải, in ra -1 (không có dấu ngoặc kép).

Nếu có lời giải, dòng này chứa một xâu độ dài $n$ chỉ gồm các chữ cái in hoa A, B, C, biểu thị cách Tiểu L bố trí xe cho $n$ ván chơi. Nếu có nhiều lời giải, in ra một lời giải bất kỳ.

Ví dụ

Dữ liệu vào 1

3 1
xcc
1
1 A 2 B

Dữ liệu ra 1

ABA

Ví dụ 2

Xem các tệp game/game2.in và game/game2.ans trong thư mục của thí sinh.

Ghi chú

Tiểu L dự định chơi 3 ván. Bản đồ ở ván 1 có loại x, thích hợp với mọi xe; bản đồ ở ván 2 và 3 có loại c, không thích hợp với xe C.

Tiểu L mong muốn: nếu dùng xe A ở ván 1 thì dùng xe B ở ván 2.

Do đó, bố trí lần lượt các xe A, B, A cho 3 ván sẽ thỏa mãn mọi điều kiện.

Bố trí lần lượt BBB hoặc BAA cho 3 ván cũng thỏa mãn mọi điều kiện và được coi là đáp án đúng. Tuy nhiên, bố trí lần lượt AAB hoặc ABC không thỏa mãn mọi điều kiện nên không được coi là đáp án đúng.

Nhiệm vụ con