题目描述

本题讨论 L-三格骨牌（L-tromino）：它由 3 个边长为 1 的正方形格子拼成 L 形。考虑旋转后，共有以下 4 种形状。

图 I.1：L-三格骨牌的四种旋转形态。

考虑一个由 $2^k\times 2^k$ 个单位格组成的正方形棋盘，其中 $k$ 为正整数。从棋盘中任意移除一个格子后，总能用互不重叠的 L-三格骨牌恰好覆盖其余所有格子，而且覆盖方式可能不唯一。

完成覆盖后，还需要给每一块 L-三格骨牌染色。若一块骨牌与所有和它共享边界的其他骨牌颜色均不同，则称它是可区分的。目标是让所有骨牌都可区分。

根据四色定理，4 种颜色一定足够。有趣的是：无论移除的是哪个格子，总存在一种覆盖方案，使得只用至多 3 种颜色便能满足要求。

给定棋盘大小和被移除格子的位置，请构造一种满足条件的覆盖与染色方案。

输入格式

第一行包含两个整数 $T,k$，分别表示测试用例数量和棋盘大小参数。$(1\le T\le 2^{10},\ 1\le k\le 10)$

保证 $T\times 2^{2k}\le 2^{22}$。

接下来 $T$ 行，每行包含两个整数 $a,b$，表示该测试用例中被移除的是第 $a$ 行第 $b$ 列的格子。$(1\le a,b\le 2^k)$

输出格式

对于每个测试用例，输出 $2^k$ 行，每行包含 $2^k$ 个字符，表示棋盘的覆盖与染色结果。

• 字符 a、b、c 表示三种颜色；
• 被移除的格子用字符 @ 表示；
• 同一块 L-三格骨牌覆盖的三个格子必须使用相同字符；
• 两块共享一段边界的 L-三格骨牌颜色必须不同。

任意满足条件的方案均可输出。

样例

输入样例 1

2 1
1 2
2 2

输出样例 1

a@
aa
bb
b@

输入样例 2

1 3
7 6

输出样例 2

bbccaacc
baacabbc
ccabcbaa
cabbccab
aaccaabb
bbcbbacc
bcabc@bc
ccaaccbb

说明

图 I.2：红色实线两侧的相邻 L-三格骨牌颜色相同，因此该方案错误。

图 I.3：在 $2^3\times 2^3$ 棋盘中，当 $a=7,b=6$ 时的一种正确方案。