Có rất nhiều bài toán về tô màu và lát gạch. Bài toán này cũng là một trong số đó, xoay quanh L-tromino, một hình được tạo thành bằng cách ghép 3 ô vuông đơn vị (cạnh bằng 1) thành hình chữ L. Có 4 hình dạng của L-tromino (tính cả các phép xoay) như dưới đây:

Hình I.1: L-tromino

Xét một bảng hình vuông gồm $2^k \times 2^k$ ô vuông với $k$ là một số nguyên dương. Người ta đã biết rằng, dù loại bỏ một ô vuông ở bất kỳ vị trí nào trên bảng, phần còn lại luôn có thể được lát kín hoàn toàn bằng các quân L-tromino không chồng lên nhau. Có thể có nhiều cách khác nhau để xếp các quân L-tromino này.

Sau khi xếp các quân L-tromino, chúng ta muốn tô màu cho từng quân L-tromino sao cho tất cả các quân L-tromino đều phân biệt được với nhau. Một quân L-tromino được gọi là phân biệt được nếu nó có màu khác với tất cả các quân L-tromino khác chung cạnh với nó.

Vì các quân L-tromino này nằm trên một mặt phẳng, theo định lý bốn màu nổi tiếng, ta luôn có thể tô màu tất cả các quân L-tromino bằng tối đa 4 màu sao cho chúng phân biệt được với nhau. Thú vị hơn, dù ô vuông bị loại bỏ ở bất kỳ vị trí nào, luôn tồn tại một cách xếp các quân L-tromino sao cho có thể tô màu phân biệt tất cả các quân L-tromino bằng tối đa 3 màu.

Cho biết kích thước của bảng và vị trí của ô bị loại bỏ, hãy tìm một phương án xếp và tô màu các quân L-tromino thỏa mãn các điều kiện trên.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $T$ là số lượng bộ dữ liệu (test case) và số nguyên $k$ quyết định kích thước của bảng ($1 \le T \le 2^{10}$, $1 \le k \le 10$).

$T \times 2^{2k}$ không vượt quá $2^{22}$.

Trong $T$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a$ và $b$ cách nhau bởi một khoảng trắng, thể hiện vị trí của ô bị loại bỏ ($1 \le a, b \le 2^k$).

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra $2^k$ dòng thể hiện cách tô màu các quân L-tromino trên bảng kích thước $2^k \times 2^k$ khi ô ở hàng thứ $a$, cột thứ $b$ bị loại bỏ.

Trong đó, dòng thứ $i$ thể hiện cách xếp của hàng thứ $i$ trên bảng.

Màu của các ô phải được biểu diễn bằng một trong các ký tự a, b, c, và ô bị loại bỏ được biểu diễn bằng ký tự @. Tất nhiên, hai quân L-tromino kề cạnh nhau không được phép có cùng màu.

Ví dụ

Dữ liệu vào 1

2 1
1 2
2 2

Dữ liệu ra 1

a@
aa
bb
b@

Dữ liệu vào 2

1 3
7 6

Dữ liệu ra 2

bbccaacc
baacabbc
ccabcbaa
cabbccab
aaccaabb
bbcbbacc
bcabc@bc
ccaaccbb

Ghi chú

Hình I.2: Một câu trả lời sai vì hai quân L-tromino kề nhau qua cạnh được đánh dấu bằng đường màu đỏ nét liền có cùng màu.

Hình I.3: Một trong các câu trả lời đúng cho bảng $2^3 \times 2^3$ khi $a = 7, b = 6$.