在一个 2ᵏ × 2ᵏ 个方格组成的棋盘中，若恰有一个方格与其他方格不同（图中标记为 -1 的方格），则称该方格为特殊方格。现在用 L 型（占3个小方格）纸片覆盖棋盘上除特殊方格的所有部分，各纸片不得重叠，于是用到的纸片数恰好是 (4ᵏ - 1) / 3 。写一个程序，求覆盖方案。

如在下图中，给出的一个覆盖方案中，k = 2 ，那么就是 4 × 4 个方格，那么纸片数恰好是 5 个。

【输入描述】

输入第一行为方阵的规模，也就是数组的行列值。输入第二行两个整数，表示特殊方格的行列下标。

【输出描述】

输出覆盖后的棋盘数组。

【输入样例】

//样例1：
8
4 4

【输出样例】

//样例1：
    3    3    4    4    8    8    9    9
    3    2    2    4    8    7    7    9
    5    2    6    6   10   10    7   11
    5    5    6   -1    1   10   11   11
   13   13   14    1    1   18   19   19
   13   12   14   14   18   18   17   19
   15   12   12   16   20   17   17   21
   15   15   16   16   20   20   21   21

【参考程序】

// 爱码岛编程
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e3 + 10;
// 二维数组(下标从1开始)，tile为纸片编号
int board[MAXN][MAXN], tile = 1;

/*
 * tr, tc 棋盘的起始行列号,
 * dr, dc 为特殊方格的行列号
 * size = 2^k 表示棋盘的行数或列数
 */
void chessBoard(int tr, int tc, int dr, int dc, int size) {
    int t, s;
    if (size == 1) {
        return;
    }
    t = tile++;
    s = size / 2;
    // 左上角
    if (dr < tr + s && dc < tc + s) {
        chessBoard(tr, tc, dr, dc, s);
    } else {
        board[tr + s - 1][tc + s - 1] = t;
        chessBoard(tr, tc, tr + s - 1, tc + s - 1, s);
    }
    // 右上角
    if (dr < tr + s && dc >= tc + s) {
        chessBoard(tr, tc + s, dr, dc, s);
    } else {
        board[tr + s - 1][tc + s] = t;
        chessBoard(tr, tc + s, tr + s - 1, tc + s, s);
    }
    // 左下角
    if (dr >= tr + s && dc < tc + s) {
        chessBoard(tr + s, tc, dr, dc, s);
    } else {
        board[tr + s][tc + s - 1] = t;
        chessBoard(tr + s, tc, tr + s, tc + s - 1, s);
    }
    // 右下角
    if (dr >= tr + s && dc >= tc + s) {
        chessBoard(tr + s, tc + s, dr, dc, s);
    } else {
        board[tr + s][tc + s] = t;
        chessBoard(tr + s, tc + s, tr + s, tc + s, s);
    }
}

int main() {
    // size = 2^k 行数和列数：2、4、8、16、32、64
    int k, size, dr, dc;
    cin >> k;
    size = pow(2, k); // k=3, size=8
    cin >> dr >> dc;  // 讲解用的是 4 4

    board[dr][dc] = -1;
    chessBoard(1, 1, dr, dc, size);

    //打印
    for (int i = 1; i <= size; i++) {
        for (int j = 1; j <= size; j++) {
            cout << setw(5) << board[i][j];
        }
        cout << endl;
    }
    return 0;
}