1913_算法设计例题：棋盘覆盖（分治）

在一个2^k × 2^k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的棋盘上除特殊方格以外的所有方格，L型骨牌不能旋转，且任何两个L型骨牌不得重叠覆盖。

棋盘和标记为红色的特殊方格                      4种L型骨牌                          

第一行是一个T，表示案例数。对于每一个案例，有三个数K，X，Y分别表示在一个2^k × 2^k的棋盘中，在第X行第Y列有一个特殊方格。1 ≤ K ≤ 8

1 ≤ X, Y ≤ 2^k

输出这个被骨牌覆盖的棋盘，分别用a,b,c,d表示四种骨牌（分别用以下四种字符图形表示），特殊方格用*号表示。

aa      bb    c      d
a        b    cc    dd

具体输出见sample Output

2
2 1 2
1 1 1

c*bb
ccdb
cddd
ccdd
*d
dd