Il existe de nombreux problèmes de coloriage et de pavage. Ce problème est l'un d'entre eux et s'intéresse aux L-trominos, qui sont des formes constituées de 3 tuiles carrées de côté 1 assemblées en forme de L. Il existe 4 orientations possibles pour un L-tromino (en incluant les rotations), comme illustré ci-dessous.

Figure I.1 : L-trominos

Pour un entier positif $k$, considérons une grille carrée composée de $2^k \times 2^k$ tuiles. Il est connu que, quelle que soit la position de la tuile que l'on retire de la grille, la partie restante peut toujours être pavée sans chevauchement par des L-trominos. Il peut y avoir plusieurs façons de disposer ces L-trominos.

Après avoir disposé les L-trominos, nous voulons colorier chacun d'eux de manière à ce qu'ils soient tous distinguables. On dit que les L-trominos sont distinguables si chaque L-tromino a une couleur différente de tous les autres L-trominos avec lesquels il partage un côté.

Comme ces L-trominos sont disposés sur un plan, le célèbre théorème des quatre couleurs garantit qu'il est possible de les colorier en utilisant au plus 4 couleurs de sorte qu'ils soient tous distinguables. De manière intéressante, quelle que soit la position de la tuile retirée, il existe toujours une configuration de pavage qui peut être coloriée avec au plus 3 couleurs de sorte que tous les L-trominos soient distinguables.

Étant donné la taille de la grille et la position de la tuile retirée, trouvez un exemple de disposition et de coloriage des L-trominos respectant les conditions ci-dessus.

Entrée

La première ligne contient l'entier $T$, le nombre total de cas de test, et l'entier $k$ qui détermine la taille de la grille ($1 \le T \le 2^{10}$, $1 \le k \le 10$).

On a $T \times 2^{2k} \le 2^{22}$.

Chacune des $T$ lignes suivantes contient deux entiers $a$ et $b$ séparés par un espace, représentant les coordonnées de la tuile retirée ($1 \le a, b \le 2^k$).

Sortie

Pour chaque cas de test, affichez le coloriage des L-trominos sur la grille de taille $2^k \times 2^k$ lorsque la tuile située à la $a$-ème ligne et à la $b$-ème colonne est retirée, sur $2^k$ lignes.

La $i$-ème ligne représente la configuration de la $i$-ème ligne de la grille.

Les couleurs des tuiles sont représentées par les caractères a, b ou c, et la tuile retirée est représentée par @. Bien entendu, deux L-trominos partageant un côté ne peuvent pas avoir la même couleur.

Exemples

Entrée 1

2 1
1 2
2 2

Sortie 1

a@
aa
bb
b@

Entrée 2

1 3
7 6

Sortie 2

bbccaacc
baacabbc
ccabcbaa
cabbccab
aaccaabb
bbcbbacc
bcabc@bc
ccaaccbb

Remarque

Figure I.2 : Mauvaise réponse car deux L-trominos adjacents ont la même couleur le long du segment rouge continu.

Figure I.3 : Une des réponses possibles pour une grille de taille $2^3 \times 2^3$ avec $a = 7, b = 6$.