QOJ.ac

QOJ

Discussion #1196 for Problem #16206. L 型覆盖

Type: Editorial

Status: Open

Posted by: lc20110802

Posted at: 2026-03-03 20:03:27

Last updated: 2026-03-03 20:20:02

Back to Problem

Editorial for Problem #16206

首先将题目转化为更符合直觉的面覆盖：

接着，可以通过状态压缩通过 $N \in \{1, 2, 3\}, M$ 较小的部分分，观察到 dp 数组有循环节，可以预处理出循环节通过 $M$ 较大的情况。

题目的上界显然为 $N(M+1) + M(N+1)$ 除以 $3$ 上取整，当 $N = 3$ 时能够取到上界。$N$ 越大，构造的自由度越高，猜测之后均能取到上界。

考虑递归构造，我们定义：

  • 零类网格图：题中所给的网格图，有 $N(M+1) + M(N+1)$ 条边。
  • 一类网格图：题中所给的网格图同时去掉上边和左边，有 $2NM$ 条边。
  • 二类网格图：题中所给的网格图去掉上边，有 $N(M+1) + M$ 条边。
  • 三类网格图：题中所给的网格图去掉左边，有 $N + M(N+1)$ 条边。

观察可知，一类网格图较小的有解情况为 $N = 6, M \in {4, 6, 7}$，当然也可以将 $N, M$ 交换。 而二、三类则限制更宽，较小的有 $N = 6, M \in {4, 5, 6, 7, 9}$。

因此，我们可以通过在最下方构造 $N = 6$ 的二类网格图来得到 $N \leftarrow N + 6$ 的答案，由对称性也可以得到 $M \leftarrow M + 6$ 的答案。而二类网格图又可以由上面较小的二类和一类组成。

经过这几种操作，我们可以分成几种情况讨论：

  • $N \le 10, M \le 10$，可以直接用舞蹈链解决。
  • $N \in {4, 5}$，可以直接使用若干三类网格图。
  • $N \in {1, 2, 3}$ 可以使用有循环节的状态压缩。
  • $M \in {1, 2, 3, 4, 5}$ 同理。

这样我们就解决了这个题，然而代码实现有些困难。

#include <bits/stdc++.h>
using namespace std;

#define FOR(x, y, z) for(int (x) = (y); (x) <= (z); (x)++)
#define ROF(x, y, z) for(int (x) = (y); (x) >= (z); (x)--)
#define mp make_pair
#define pb push_back

const int M = 400;
int n, m, nn, mm;
vector<vector<int> > cc, sq;

vector<vector<int> > puzzles = {{1, 3}, {2, 4}, {7, 9}, {6, 8}, {1, 2, 3}, {6, 7, 8}, {1, 3, 8}, {2, 4, 9}, {4, 6}, {5, 7}, {9, 11}, {10, 12}, {5, 6, 7}, {10, 11, 12}, {4, 9, 11}, {5, 10, 12}, {3, 6}, {4, 7}, {8, 11}, {9, 12}, {3, 6, 7}, {8, 11, 12}, {3, 8, 11}, {4, 9, 12}, {1, 4}, {2, 5}, {6, 9}, {7, 10}, {1, 2, 5}, {6, 7, 10}, {1, 4, 9}, {2, 5, 10}};
vector<vector<int> > puzzles3 = {{1,3}, {2,4}, {6,8}, {7,9}, {11,13}, {12,14}, {1,2,3}, {6,7,8}, {11,12,13}, {1,3,8}, {2,4,9}, {6,8,13}, {7,9,14}, {3,6}, {4,7}, {8,11}, {9,12}, {13,16}, {14,17}, {3,6,7}, {8,11,12}, {13,16,17}, {3,8,11}, {4,9,12}, {8,13,16}, {9,14,17}, {4,6}, {5,7}, {9,11}, {10,12}, {14,16}, {15,17}, {5,6,7}, {10,11,12}, {15,16,17}, {4,9,11}, {5,10,12}, {9,14,16}, {10,15,17}, {1,4}, {2,5}, {6,9}, {7,10}, {11,14}, {12,15}, {1,2,5}, {6,7,10}, {11,12,15}, {1,4,9}, {2,5,10}, {6,9,14}, {7,10,15}};
vector<int> useful = {0, 4, 7, 9, 23, 32, 36, 41, 44, 45, 47, 51, 55, 63, 100, 121, 132, 133, 151, 160, 165, 167, 168, 172, 175, 191, 231, 245, 297, 301, 365, 511, 1028, 1029, 1037, 1047, 1055, 1156, 1175, 1188, 1280, 1285, 1392, 1453, 1567};
vector<int> iuf(4100, 1e9);
vector<int> useful3 = {0, 4, 5, 7, 9, 23, 32, 39, 44, 63, 100, 109, 117, 132, 133, 151, 160, 167, 228, 231, 245, 247, 365, 383, 493, 759, 1023, 1024, 1028, 1037, 1047, 1060, 1064, 1071, 1079, 1136, 1149, 1156, 1196, 1215, 1268, 1269, 1281, 1320, 1325, 1327, 1381, 1444, 1453, 1455, 1463, 1519, 1533, 1535, 1655, 2047, 3207, 3263, 3623, 3701, 3949, 3967, 4105, 4217, 4228, 4247, 4268, 4287, 4855, 5293, 5373, 6143, 7871, 9252, 9271, 11687, 16383, 19565, 32781, 32900, 32901, 32905, 32933, 32940, 32941, 32959, 33005, 33012, 33013, 33197, 33277, 33535, 33805, 38017, 41471, 46509};
vector<int> iuf3(200000, 1e9);
vector<vector<int> > dp(M + 2, vector<int>(50, 1e9));
vector<vector<int> > fr(M + 2, vector<int>(50, 1e9));
vector<vector<int> > dp3(M + 2, vector<int>(100, 1e9));
vector<vector<int> > fr3(M + 2, vector<int>(100, 1e9));

struct Node{
    int a[15][15];
    int b[15][15];
};
Node ANS[20][20][4];

void init(){
ANS[1][1][0] = {
{{1},{2}},
{{2, 1}}
};
ANS[2][1][0] = {
{{1},{3},{2}},
{{2, 1},{2, 3}}
};
ANS[3][1][0] = {
{{1},{2},{4},{3}},
{{1, 2},{1, 3},{4, 3}}
};
ANS[4][1][0] = {
{{1},{2},{5},{3},{4}},
{{2, 1},{3, 1},{3, 5},{4, 5}}
};
ANS[5][1][0] = {
{{1},{3},{2},{6},{4},{5}},
{{1, 2},{3, 2},{3, 4},{6, 4},{6, 5}}
};
ANS[6][1][0] = {
{{1},{2},{4},{3},{7},{5},{6}},
{{1, 2},{1, 3},{4, 3},{4, 5},{7, 5},{7, 6}}
};
ANS[7][1][0] = {
{{1},{3},{2},{5},{4},{8},{6},{7}},
{{1, 2},{3, 2},{3, 4},{5, 4},{5, 6},{8, 6},{8, 7}}
};
ANS[8][1][0] = {
{{1},{3},{2},{5},{4},{7},{6},{9},{8}},
{{2, 1},{2, 3},{4, 3},{4, 5},{6, 5},{6, 7},{8, 7},{8, 9}}
};
ANS[9][1][0] = {
{{1},{3},{2},{5},{4},{7},{6},{10},{8},{9}},
{{1, 2},{3, 2},{3, 4},{5, 4},{5, 6},{7, 6},{7, 8},{10, 8},{10, 9}}
};
ANS[10][1][0] = {
{{1},{3},{2},{5},{4},{7},{6},{9},{8},{11},{10}},
{{2, 1},{2, 3},{4, 3},{4, 5},{6, 5},{6, 7},{8, 7},{8, 9},{10, 9},{10, 11}}
};
ANS[1][2][0] = {
{{1, 2},{3, 3}},
{{3, 1, 2}}
};
ANS[2][2][0] = {
{{1, 2},{4, 4},{3, 3}},
{{4, 1, 2},{3, 1, 2}}
};
ANS[3][2][0] = {
{{1, 2},{3, 3},{5, 5},{4, 6}},
{{3, 1, 2},{4, 1, 2},{4, 6, 5}}
};
ANS[4][2][0] = {
{{1, 2},{3, 3},{4, 4},{5, 8},{6, 7}},
{{3, 1, 2},{4, 5, 2},{6, 5, 7},{6, 8, 7}}
};
ANS[5][2][0] = {
{{1, 2},{3, 4},{5, 6},{7, 7},{9, 9},{8, 10}},
{{3, 1, 2},{5, 4, 2},{7, 4, 6},{8, 10, 6},{8, 10, 9}}
};
ANS[6][2][0] = {
{{1, 2},{3, 3},{5, 5},{4, 7},{8, 6},{10, 10},{9, 11}},
{{3, 1, 2},{4, 1, 2},{4, 6, 5},{8, 6, 7},{9, 11, 7},{9, 11, 10}}
};
ANS[7][2][0] = {
{{1, 2},{4, 4},{6, 3},{5, 5},{10, 7},{11, 8},{12, 12},{13, 9}},
{{1, 2, 3},{4, 2, 3},{6, 7, 5},{6, 7, 8},{10, 11, 8},{10, 13, 9},{12, 13, 9}}
};
ANS[8][2][0] = {
{{1, 2},{3, 3},{5, 5},{4, 7},{9, 6},{8, 10},{11, 11},{13, 13},{12, 14}},
{{3, 1, 2},{4, 1, 2},{4, 6, 5},{8, 6, 7},{8, 9, 7},{11, 9, 10},{12, 14, 10},{12, 14, 13}}
};
ANS[9][2][0] = {
{{1, 2},{3, 4},{5, 5},{7, 7},{9, 6},{8, 11},{12, 10},{13, 13},{15, 15},{16, 14}},
{{1, 4, 2},{1, 3, 2},{5, 3, 6},{7, 8, 6},{9, 8, 10},{9, 11, 10},{12, 11, 13},{12, 16, 14},{15, 16, 14}}
};
ANS[10][2][0] = {
{{1, 2},{4, 5},{6, 3},{7, 7},{9, 9},{8, 12},{10, 13},{11, 14},{15, 15},{17, 17},{16, 18}},
{{1, 3, 2},{4, 3, 5},{4, 6, 5},{8, 6, 7},{8, 10, 9},{11, 10, 12},{11, 13, 12},{15, 13, 14},{16, 18, 14},{16, 18, 17}}
};
ANS[1][3][0] = {
{{1, 4, 4},{2, 2, 3}},
{{1, 4, 2, 3}}
};
ANS[2][3][0] = {
{{1, 2, 2},{3, 3, 6},{4, 4, 5}},
{{3, 1, 5, 2},{4, 1, 5, 6}}
};
ANS[3][3][0] = {
{{1, 1, 2},{7, 6, 6},{3, 8, 8},{4, 4, 5}},
{{3, 6, 1, 2},{3, 7, 5, 2},{4, 7, 5, 8}}
};
ANS[4][3][0] = {
{{1, 1, 2},{5, 10, 10},{3, 11, 11},{6, 6, 9},{4, 7, 8}},
{{3, 5, 1, 2},{3, 10, 9, 11},{4, 7, 9, 8},{4, 7, 6, 8}}
};
ANS[5][3][0] = {
{{1, 2, 2},{6, 6, 10},{3, 7, 7},{4, 4, 9},{8, 12, 12},{5, 13, 11}},
{{3, 1, 6, 2},{3, 7, 9, 10},{4, 8, 9, 10},{5, 8, 13, 11},{5, 12, 13, 11}}
};
ANS[6][3][0] = {
{{1, 1, 2},{7, 4, 4},{8, 8, 3},{9, 10, 10},{11, 11, 5},{14, 14, 12},{13, 15, 6}},
{{1, 4, 2, 3},{7, 9, 2, 3},{7, 9, 8, 5},{11, 10, 12, 5},{13, 15, 12, 6},{13, 15, 14, 6}}
};
ANS[7][3][0] = {
{{1, 2, 3},{6, 5, 5},{7, 7, 4},{15, 11, 11},{12, 12, 8},{14, 9, 9},{17, 17, 13},{16, 18, 10}},
{{1, 2, 3, 4},{6, 5, 3, 4},{6, 11, 7, 8},{14, 15, 12, 8},{14, 15, 13, 9},{16, 18, 13, 10},{16, 18, 17, 10}}
};
ANS[8][3][0] = {
{{1, 2, 3},{5, 5, 4},{6, 6, 7},{11, 12, 12},{8, 13, 13},{15, 15, 14},{9, 16, 16},{17, 19, 19},{10, 20, 18}},
{{5, 1, 2, 3},{6, 1, 4, 3},{8, 12, 4, 7},{8, 11, 14, 7},{9, 11, 14, 13},{9, 17, 15, 16},{10, 17, 20, 18},{10, 19, 20, 18}}
};
ANS[9][3][0] = {
{{1, 2, 2},{3, 3, 5},{8, 4, 6},{7, 9, 9},{10, 10, 14},{22, 22, 20},{11, 21, 18},{17, 19, 19},{12, 16, 16},{13, 13, 15}},
{{3, 1, 4, 2},{7, 1, 4, 5},{7, 8, 6, 5},{10, 8, 6, 9},{11, 21, 22, 14},{11, 21, 20, 14},{12, 19, 20, 18},{12, 17, 15, 18},{13, 17, 15, 16}}
};
ANS[10][3][0] = {
{{1, 2, 3},{5, 6, 6},{4, 7, 7},{8, 8, 10},{13, 13, 9},{11, 12, 17},{25, 25, 23},{14, 24, 21},{20, 22, 22},{15, 19, 19},{16, 16, 18}},
{{4, 1, 2, 3},{4, 5, 2, 6},{8, 5, 9, 7},{11, 12, 9, 10},{11, 12, 13, 10},{14, 24, 25, 17},{14, 24, 23, 17},{15, 22, 23, 21},{15, 20, 18, 21},{16, 20, 18, 19}}
};
ANS[1][4][0] = {
{{1, 5, 5, 4},{2, 2, 3, 3}},
{{1, 5, 2, 4, 3}}
};
ANS[2][4][0] = {
{{1, 1, 2, 2},{4, 6, 7, 7},{3, 5, 5, 8}},
{{3, 4, 1, 8, 2},{3, 5, 6, 8, 7}}
};
ANS[3][4][0] = {
{{1, 11, 11, 8},{3, 10, 9, 9},{4, 4, 7, 7},{2, 2, 5, 6}},
{{1, 10, 9, 11, 8},{1, 3, 7, 5, 8},{2, 3, 4, 5, 6}}
};
ANS[4][4][0] = {
{{1, 1, 6, 6},{4, 4, 7, 8},{2, 11, 9, 9},{3, 10, 14, 14},{5, 12, 12, 13}},
{{1, 2, 4, 7, 6},{3, 2, 10, 8, 9},{3, 11, 10, 8, 13},{5, 11, 14, 12, 13}}
};
ANS[5][4][0] = {
{{1, 1, 16, 15},{3, 17, 17, 14},{4, 2, 13, 13},{5, 5, 9, 11},{6, 8, 8, 12},{7, 7, 10, 10}},
{{1, 2, 16, 17, 15},{3, 2, 16, 14, 15},{5, 4, 13, 14, 12},{6, 4, 9, 11, 12},{7, 8, 9, 11, 10}}
};
ANS[6][4][0] = {
{{1, 2, 2, 3},{5, 5, 6, 10},{4, 13, 12, 12},{7, 7, 16, 11},{20, 19, 17, 17},{8, 18, 18, 14},{9, 9, 15, 15}},
{{4, 1, 6, 2, 3},{4, 1, 5, 10, 11},{7, 13, 12, 10, 11},{8, 13, 17, 16, 14},{8, 20, 19, 16, 14},{9, 20, 19, 18, 15}}
};
ANS[7][4][0] = {
{{1, 2, 3, 4},{6, 6, 5, 5},{8, 8, 9, 10},{7, 14, 14, 11},{16, 16, 17, 17},{12, 15, 18, 18},{20, 20, 22, 22},{13, 21, 23, 19}},
{{6, 1, 2, 3, 4},{7, 1, 2, 3, 5},{7, 14, 8, 9, 10},{12, 15, 16, 11, 10},{12, 15, 17, 11, 18},{13, 21, 20, 23, 19},{13, 21, 22, 23, 19}}
};
ANS[8][4][0] = {
{{1, 1, 6, 6},{3, 5, 7, 7},{4, 2, 8, 10},{15, 15, 14, 9},{16, 17, 11, 11},{18, 18, 20, 20},{21, 21, 19, 12},{23, 23, 25, 25},{22, 24, 26, 13}},
{{1, 2, 6, 8, 7},{3, 2, 5, 8, 9},{4, 16, 5, 10, 9},{15, 16, 14, 10, 11},{18, 17, 14, 19, 12},{21, 17, 20, 19, 12},{22, 24, 23, 26, 13},{22, 24, 25, 26, 13}}
};
ANS[9][4][0] = {
{{1, 2, 2, 3},{7, 5, 5, 4},{9, 9, 6, 13},{8, 16, 15, 15},{17, 17, 18, 14},{10, 22, 19, 19},{23, 23, 24, 24},{11, 27, 27, 20},{25, 25, 26, 26},{12, 28, 29, 21}},
{{1, 5, 6, 2, 3},{8, 7, 6, 4, 3},{8, 7, 9, 13, 14},{10, 16, 15, 13, 14},{10, 16, 17, 18, 19},{11, 22, 24, 18, 20},{11, 22, 23, 27, 20},{12, 28, 25, 29, 21},{12, 28, 26, 29, 21}}
};
ANS[10][4][0] = {
{{1, 2, 3, 4},{6, 6, 5, 5},{8, 7, 14, 14},{9, 10, 10, 16},{11, 13, 17, 15},{12, 12, 18, 18},{25, 25, 23, 20},{26, 24, 24, 19},{27, 27, 21, 21},{29, 29, 31, 31},{28, 30, 32, 22}},
{{1, 7, 2, 3, 4},{6, 7, 5, 3, 4},{8, 10, 13, 15, 14},{8, 9, 13, 15, 16},{11, 9, 18, 17, 16},{11, 26, 12, 17, 19},{25, 26, 23, 20, 19},{27, 24, 23, 20, 21},{28, 30, 29, 32, 22},{28, 30, 31, 32, 22}}
};
ANS[1][5][0] = {
{{1, 1, 2, 2, 3},{6, 5, 5, 4, 4}},
{{6, 5, 1, 4, 2, 3}}
};
ANS[2][5][0] = {
{{1, 9, 8, 8, 6},{3, 10, 10, 7, 7},{2, 2, 4, 4, 5}},
{{1, 9, 8, 7, 6, 5},{1, 3, 2, 10, 4, 5}}
};
ANS[3][5][0] = {
{{1, 2, 2, 3, 3},{4, 4, 11, 11, 12},{6, 6, 10, 13, 13},{5, 7, 8, 9, 9}},
{{4, 1, 10, 2, 11, 3},{5, 7, 10, 8, 12, 13},{5, 7, 6, 8, 12, 9}}
};
ANS[4][5][0] = {
{{1, 2, 3, 4, 4},{5, 5, 8, 9, 9},{11, 12, 12, 10, 16},{6, 13, 13, 17, 17},{7, 7, 14, 15, 15}},
{{5, 1, 2, 3, 10, 4},{6, 12, 2, 8, 10, 9},{6, 11, 14, 8, 16, 17},{7, 11, 14, 13, 16, 15}}
};
ANS[5][5][0] = {
{{1, 1, 2, 3, 3},{7, 8, 8, 9, 9},{4, 11, 11, 10, 14},{13, 12, 16, 16, 15},{5, 20, 20, 18, 18},{6, 6, 19, 17, 17}},
{{4, 8, 1, 2, 10, 3},{4, 7, 12, 2, 10, 9},{5, 7, 12, 11, 16, 14},{5, 13, 19, 20, 15, 14},{6, 13, 19, 18, 15, 17}}
};
ANS[6][5][0] = {
{{1, 1, 2, 2, 3},{7, 7, 9, 9, 10},{4, 8, 11, 12, 12},{14, 13, 13, 21, 21},{5, 15, 20, 18, 23},{16, 16, 19, 19, 22},{6, 17, 17, 24, 24}},
{{4, 8, 1, 11, 2, 3},{4, 8, 7, 11, 9, 10},{5, 13, 15, 12, 18, 10},{5, 14, 15, 21, 18, 22},{6, 14, 19, 20, 23, 22},{6, 17, 16, 20, 23, 24}}
};
ANS[7][5][0] = {
{{1, 2, 2, 3, 4},{14, 14, 15, 5, 5},{6, 16, 16, 18, 19},{7, 7, 20, 20, 17},{13, 12, 12, 24, 24},{8, 11, 21, 21, 22},{9, 9, 25, 27, 27},{10, 10, 23, 28, 26}},
{{6, 1, 14, 2, 3, 4},{6, 16, 15, 5, 17, 4},{7, 13, 15, 18, 17, 19},{8, 13, 20, 18, 22, 19},{8, 12, 21, 25, 22, 24},{9, 11, 23, 25, 28, 26},{10, 11, 23, 27, 28, 26}}
};
ANS[8][5][0] = {
{{1, 1, 2, 2, 3},{4, 4, 12, 11, 11},{7, 5, 16, 16, 17},{6, 15, 19, 19, 18},{13, 20, 20, 22, 22},{8, 21, 28, 28, 30},{14, 23, 29, 31, 31},{9, 24, 24, 27, 27},{10, 10, 25, 25, 26}},
{{4, 5, 1, 11, 2, 3},{6, 5, 15, 12, 16, 3},{6, 7, 15, 12, 19, 17},{8, 7, 21, 20, 18, 17},{8, 13, 21, 29, 18, 22},{9, 13, 28, 29, 30, 31},{9, 14, 23, 27, 30, 26},{10, 14, 23, 24, 25, 26}}
};
ANS[9][5][0] = {
{{1, 1, 2, 3, 4},{6, 6, 7, 5, 5},{10, 8, 11, 14, 14},{9, 12, 13, 13, 21},{16, 17, 17, 22, 22},{15, 18, 18, 23, 23},{29, 35, 35, 24, 24},{19, 34, 33, 25, 27},{30, 30, 32, 32, 26},{20, 31, 31, 28, 28}},
{{6, 8, 1, 2, 3, 4},{9, 8, 7, 5, 3, 4},{9, 10, 7, 11, 13, 14},{15, 10, 12, 11, 21, 22},{15, 16, 12, 17, 21, 23},{19, 16, 34, 18, 25, 24},{19, 29, 34, 35, 25, 26},{20, 29, 30, 33, 27, 26},{20, 31, 32, 33, 27, 28}}
};
ANS[10][5][0] = {
{{1, 1, 2, 3, 3},{4, 4, 37, 38, 38},{7, 5, 36, 36, 39},{6, 18, 33, 35, 35},{8, 8, 34, 30, 32},{17, 17, 22, 22, 31},{9, 21, 21, 29, 29},{16, 19, 19, 28, 28},{10, 20, 26, 27, 24},{12, 12, 23, 23, 25},{11, 13, 14, 15, 15}},
{{4, 5, 1, 2, 39, 3},{6, 5, 36, 37, 39, 38},{6, 7, 34, 37, 32, 35},{8, 18, 34, 33, 32, 31},{9, 18, 17, 33, 30, 31},{9, 16, 22, 21, 30, 29},{10, 16, 20, 26, 27, 28},{10, 19, 20, 26, 27, 25},{11, 13, 23, 14, 24, 25},{11, 13, 12, 14, 24, 15}}
};
ANS[1][6][0] = {
{{1, 2, 2, 3, 3, 4},{7, 7, 6, 6, 5, 5}},
{{7, 1, 6, 2, 5, 3, 4}}
};
ANS[2][6][0] = {
{{1, 1, 7, 9, 9, 10},{2, 2, 8, 8, 11, 11},{3, 4, 4, 5, 6, 6}},
{{1, 3, 7, 9, 8, 10, 11},{2, 3, 7, 4, 5, 10, 6}}
};
ANS[3][6][0] = {
{{1, 1, 10, 10, 11, 11},{3, 2, 2, 13, 13, 14},{5, 5, 9, 12, 15, 15},{4, 6, 6, 7, 8, 8}},
{{1, 2, 9, 12, 10, 13, 11},{3, 4, 9, 12, 7, 14, 15},{3, 4, 5, 6, 7, 14, 8}}
};
ANS[4][6][0] = {
{{1, 3, 4, 4, 5, 6},{2, 9, 9, 8, 8, 7},{19, 17, 17, 15, 10, 10},{20, 20, 14, 14, 12, 12},{18, 18, 16, 13, 13, 11}},
{{1, 2, 3, 8, 4, 5, 6},{1, 17, 3, 9, 10, 7, 6},{20, 19, 16, 15, 14, 7, 11},{18, 19, 16, 15, 12, 13, 11}}
};
ANS[5][6][0] = {
{{1, 2, 3, 4, 4, 5},{8, 8, 6, 6, 7, 7},{9, 14, 16, 16, 18, 18},{13, 13, 22, 24, 24, 17},{10, 12, 12, 23, 20, 20},{11, 11, 15, 15, 21, 19}},
{{1, 9, 2, 3, 7, 4, 5},{8, 9, 2, 3, 6, 17, 5},{10, 14, 16, 24, 23, 17, 18},{10, 14, 13, 22, 23, 21, 19},{11, 12, 15, 22, 20, 21, 19}}
};
ANS[6][6][0] = {
{{1, 3, 3, 8, 8, 10},{2, 4, 5, 5, 12, 12},{6, 7, 7, 17, 17, 11},{9, 19, 19, 14, 13, 13},{23, 23, 22, 22, 20, 18},{25, 25, 27, 27, 21, 15},{24, 26, 26, 28, 16, 16}},
{{1, 3, 5, 8, 12, 10, 11},{1, 2, 4, 7, 14, 10, 11},{6, 2, 4, 17, 14, 18, 13},{6, 9, 23, 19, 21, 18, 15},{24, 9, 22, 28, 21, 20, 15},{24, 26, 25, 28, 27, 20, 16}}
};
ANS[7][6][0] = {
{{1, 1, 2, 2, 3, 3},{4, 9, 9, 10, 10, 12},{15, 15, 16, 16, 11, 13},{5, 14, 17, 18, 23, 23},{6, 19, 19, 22, 22, 25},{7, 7, 20, 30, 30, 24},{21, 32, 32, 29, 27, 27},{8, 33, 31, 28, 28, 26}},
{{4, 9, 1, 10, 2, 11, 3},{5, 14, 16, 17, 18, 11, 12},{5, 14, 15, 17, 18, 13, 12},{6, 19, 20, 22, 23, 13, 24},{7, 21, 20, 30, 29, 25, 24},{8, 21, 33, 31, 29, 25, 26},{8, 32, 33, 31, 27, 28, 26}}
};
ANS[8][6][0] = {
{{1, 1, 2, 3, 4, 4},{5, 5, 11, 12, 12, 13},{6, 16, 16, 15, 15, 14},{7, 17, 17, 18, 18, 19},{23, 22, 22, 20, 21, 21},{8, 24, 25, 36, 35, 35},{9, 9, 37, 37, 32, 34},{26, 26, 30, 31, 31, 33},{10, 27, 28, 28, 29, 29}},
{{5, 6, 1, 2, 3, 12, 4},{7, 6, 11, 16, 3, 15, 13},{7, 17, 11, 18, 20, 14, 13},{8, 22, 24, 25, 20, 14, 19},{8, 23, 24, 25, 21, 34, 19},{9, 23, 30, 36, 35, 34, 33},{10, 27, 30, 36, 37, 32, 33},{10, 27, 26, 31, 28, 32, 29}}
};
ANS[9][6][0] = {
{{1, 1, 5, 5, 7, 8},{3, 4, 4, 10, 9, 9},{2, 13, 6, 11, 12, 12},{17, 14, 14, 15, 15, 18},{16, 26, 25, 25, 19, 19},{28, 28, 24, 24, 23, 23},{30, 30, 27, 38, 40, 20},{32, 29, 35, 35, 39, 41},{31, 34, 34, 37, 37, 21},{33, 33, 36, 36, 22, 22}},
{{1, 2, 6, 4, 5, 7, 8},{3, 2, 6, 10, 9, 7, 8},{3, 16, 13, 10, 11, 15, 12},{17, 16, 13, 14, 11, 18, 19},{17, 26, 25, 27, 24, 18, 20},{28, 26, 29, 27, 23, 41, 20},{30, 31, 29, 38, 40, 41, 21},{32, 31, 35, 38, 40, 39, 21},{32, 34, 33, 37, 36, 39, 22}}
};
ANS[10][6][0] = {
{{1, 2, 3, 4, 4, 5},{7, 7, 17, 17, 18, 18},{6, 21, 28, 27, 27, 30},{20, 20, 26, 26, 32, 29},{8, 19, 19, 31, 34, 34},{9, 9, 22, 22, 36, 36},{10, 10, 33, 35, 39, 39},{13, 11, 23, 41, 41, 38},{12, 24, 24, 37, 43, 40},{15, 15, 25, 42, 46, 46},{14, 16, 16, 44, 44, 45}},
{{6, 1, 2, 3, 17, 4, 5},{6, 1, 7, 27, 18, 29, 5},{8, 21, 26, 28, 31, 29, 30},{8, 21, 20, 28, 31, 32, 30},{9, 19, 22, 33, 35, 32, 34},{10, 11, 23, 33, 35, 38, 36},{12, 11, 23, 37, 39, 38, 40},{12, 13, 25, 37, 42, 41, 40},{14, 13, 25, 24, 42, 43, 45},{14, 16, 15, 44, 46, 43, 45}}
};
ANS[1][7][0] = {
{{1, 1, 8, 8, 7, 7, 6},{2, 3, 3, 4, 4, 5, 5}},
{{1, 2, 8, 3, 7, 4, 6, 5}}
};
ANS[2][7][0] = {
{{1, 5, 5, 7, 7, 8, 8},{3, 3, 6, 6, 11, 11, 13},{2, 4, 4, 9, 10, 12, 12}},
{{1, 2, 6, 5, 9, 7, 13, 8},{1, 2, 3, 4, 9, 10, 11, 12}}
};
ANS[3][7][0] = {
{{1, 1, 7, 14, 14, 16, 16},{3, 2, 2, 15, 15, 17, 17},{5, 6, 6, 11, 12, 12, 18},{4, 4, 8, 9, 10, 13, 13}},
{{1, 2, 7, 15, 11, 14, 18, 16},{3, 6, 7, 8, 11, 10, 18, 17},{3, 5, 4, 8, 9, 10, 12, 13}}
};
ANS[4][7][0] = {
{{1, 1, 2, 3, 4, 4, 5},{6, 11, 12, 12, 13, 9, 9},{10, 15, 15, 17, 20, 20, 22},{7, 14, 14, 18, 18, 23, 23},{8, 8, 16, 16, 19, 21, 21}},
{{6, 10, 1, 2, 3, 9, 4, 5},{7, 10, 11, 2, 12, 13, 20, 5},{7, 15, 11, 17, 19, 13, 22, 23},{8, 14, 16, 17, 19, 18, 22, 21}}
};
ANS[5][7][0] = {
{{1, 1, 6, 7, 7, 8, 8},{3, 5, 5, 27, 27, 24, 24},{4, 2, 19, 28, 26, 26, 25},{10, 9, 18, 18, 21, 21, 23},{12, 12, 14, 14, 20, 22, 22},{11, 13, 13, 15, 16, 16, 17}},
{{1, 2, 6, 5, 28, 7, 25, 8},{3, 2, 9, 27, 28, 24, 25, 23},{3, 4, 9, 19, 18, 20, 26, 23},{10, 11, 12, 19, 15, 20, 21, 17},{10, 11, 14, 13, 15, 22, 16, 17}}
};
ANS[6][7][0] = {
{{1, 1, 2, 3, 3, 4, 4},{5, 5, 31, 31, 29, 23, 23},{8, 6, 32, 32, 30, 24, 22},{7, 13, 33, 28, 28, 25, 25},{12, 12, 14, 19, 27, 26, 21},{9, 11, 11, 18, 18, 20, 20},{10, 10, 15, 16, 16, 17, 17}},
{{5, 6, 1, 2, 30, 3, 24, 4},{7, 6, 31, 33, 30, 29, 24, 23},{7, 8, 32, 33, 27, 29, 26, 22},{9, 13, 12, 28, 27, 25, 26, 22},{9, 13, 14, 15, 19, 18, 21, 20},{10, 11, 14, 15, 19, 16, 21, 17}}
};
ANS[7][7][0] = {
{{1, 2, 2, 3, 4, 4, 5},{6, 11, 12, 12, 13, 14, 14},{7, 7, 21, 22, 22, 15, 15},{23, 23, 25, 25, 27, 16, 18},{8, 24, 35, 35, 28, 28, 17},{9, 9, 37, 34, 34, 30, 29},{26, 38, 38, 36, 31, 31, 19},{10, 33, 33, 32, 32, 20, 20}},
{{6, 1, 12, 2, 3, 14, 4, 5},{7, 1, 11, 22, 3, 13, 16, 15},{8, 24, 11, 21, 25, 13, 16, 17},{8, 24, 23, 21, 28, 27, 18, 17},{9, 26, 35, 34, 36, 27, 18, 19},{10, 26, 37, 38, 36, 30, 29, 19},{10, 33, 37, 32, 31, 30, 29, 20}}
};
ANS[8][7][0] = {
{{1, 2, 2, 3, 3, 4, 4},{5, 5, 10, 19, 16, 16, 18},{12, 12, 15, 15, 23, 23, 17},{6, 11, 20, 20, 21, 22, 24},{14, 14, 32, 32, 31, 25, 25},{7, 13, 34, 33, 27, 26, 26},{35, 36, 36, 40, 40, 28, 28},{8, 37, 37, 39, 42, 42, 29},{9, 9, 38, 38, 41, 43, 30}},
{{5, 1, 10, 2, 16, 3, 17, 4},{6, 11, 12, 19, 21, 22, 17, 18},{6, 11, 15, 19, 21, 22, 23, 18},{7, 13, 14, 33, 20, 27, 24, 25},{7, 13, 32, 33, 31, 27, 24, 26},{8, 36, 34, 39, 31, 40, 29, 28},{8, 35, 34, 39, 41, 43, 29, 30},{9, 35, 38, 37, 41, 43, 42, 30}}
};
ANS[9][7][0] = {
{{1, 2, 3, 3, 4, 4, 5},{10, 8, 8, 7, 7, 6, 6},{9, 12, 15, 15, 17, 17, 19},{13, 11, 20, 16, 28, 28, 18},{14, 21, 24, 24, 32, 27, 30},{23, 22, 22, 33, 33, 29, 31},{25, 26, 26, 34, 34, 35, 35},{47, 47, 40, 40, 39, 39, 38},{48, 48, 44, 44, 41, 41, 36},{46, 45, 45, 43, 42, 37, 37}},
{{1, 9, 2, 8, 3, 7, 4, 5},{10, 9, 11, 16, 17, 6, 18, 5},{10, 12, 11, 16, 15, 27, 18, 19},{13, 12, 24, 20, 28, 27, 29, 19},{13, 14, 21, 20, 32, 33, 29, 30},{23, 14, 21, 22, 32, 35, 31, 30},{23, 25, 47, 26, 40, 34, 31, 36},{46, 25, 44, 43, 39, 42, 38, 36},{46, 45, 48, 43, 41, 42, 38, 37}}
};
ANS[10][7][0] = {
{{1, 2, 3, 3, 4, 5, 6},{10, 10, 20, 20, 7, 7, 8},{23, 24, 24, 21, 22, 9, 9},{11, 29, 29, 30, 30, 33, 33},{25, 25, 31, 51, 52, 34, 35},{12, 26, 26, 53, 53, 36, 36},{13, 13, 27, 27, 49, 40, 37},{19, 18, 18, 50, 50, 38, 38},{14, 17, 28, 47, 48, 39, 39},{15, 15, 45, 46, 46, 42, 42},{16, 16, 32, 44, 44, 43, 41}},
{{10, 1, 2, 21, 3, 4, 5, 6},{11, 1, 20, 21, 7, 4, 5, 8},{11, 23, 31, 24, 22, 9, 34, 8},{12, 23, 31, 29, 22, 30, 34, 33},{12, 26, 25, 51, 52, 53, 37, 35},{13, 19, 27, 51, 52, 36, 37, 35},{14, 19, 28, 50, 48, 49, 40, 38},{14, 18, 28, 45, 48, 49, 40, 39},{15, 17, 32, 45, 47, 46, 43, 41},{16, 17, 32, 44, 47, 42, 43, 41}}
};
ANS[1][8][0] = {
{{1, 9, 9, 8, 8, 7, 7, 6},{2, 2, 3, 3, 4, 4, 5, 5}},
{{1, 9, 2, 8, 3, 7, 4, 6, 5}}
};
ANS[2][8][0] = {
{{1, 2, 2, 3, 3, 4, 5, 5},{6, 6, 9, 9, 10, 10, 13, 13},{7, 7, 8, 11, 11, 12, 12, 14}},
{{6, 1, 8, 2, 10, 3, 4, 14, 5},{7, 1, 8, 11, 9, 12, 4, 14, 13}}
};
ANS[3][8][0] = {
{{1, 2, 3, 4, 5, 9, 9, 10},{7, 7, 6, 6, 8, 8, 11, 11},{13, 13, 14, 14, 15, 15, 19, 19},{12, 16, 16, 17, 17, 18, 18, 20}},
{{7, 1, 2, 3, 4, 5, 8, 9, 10},{12, 1, 6, 3, 4, 5, 11, 20, 10},{12, 16, 13, 17, 14, 18, 15, 20, 19}}
};
ANS[4][8][0] = {
{{1, 1, 2, 2, 3, 3, 4, 5},{6, 6, 13, 13, 20, 20, 24, 24},{7, 10, 14, 16, 21, 23, 23, 26},{8, 11, 11, 17, 17, 22, 22, 25},{9, 9, 12, 15, 15, 18, 19, 19}},
{{6, 7, 1, 14, 2, 21, 3, 4, 5},{8, 7, 13, 14, 20, 21, 24, 23, 25},{8, 10, 12, 11, 16, 22, 18, 26, 25},{9, 10, 12, 15, 16, 17, 18, 26, 19}}
};
ANS[5][8][0] = {
{{1, 1, 5, 6, 6, 9, 12, 12},{3, 4, 4, 7, 8, 8, 14, 14},{2, 11, 11, 10, 10, 13, 15, 16},{29, 30, 30, 23, 23, 20, 20, 19},{28, 28, 31, 25, 25, 21, 17, 17},{27, 27, 26, 26, 24, 22, 18, 18}},
{{1, 2, 5, 6, 8, 9, 13, 15, 12},{3, 2, 5, 4, 7, 9, 13, 15, 14},{3, 11, 31, 10, 7, 23, 21, 20, 16},{28, 29, 31, 30, 24, 22, 21, 19, 16},{27, 29, 26, 25, 24, 22, 18, 19, 17}}
};
ANS[6][8][0] = {
{{1, 2, 2, 3, 4, 5, 5, 6},{8, 8, 9, 9, 17, 17, 14, 13},{7, 22, 22, 25, 25, 15, 15, 16},{10, 10, 23, 23, 24, 19, 19, 18},{20, 21, 26, 26, 31, 31, 37, 37},{11, 28, 28, 27, 33, 33, 36, 36},{12, 12, 29, 30, 32, 34, 34, 35}},
{{7, 1, 9, 2, 3, 4, 17, 5, 6},{7, 1, 8, 22, 24, 4, 14, 13, 6},{10, 21, 23, 25, 24, 15, 14, 13, 16},{11, 21, 26, 27, 31, 19, 37, 18, 16},{11, 20, 29, 27, 30, 32, 36, 18, 35},{12, 20, 29, 28, 30, 32, 33, 34, 35}}
};
ANS[7][8][0] = {
{{1, 1, 2, 2, 3, 4, 5, 6},{9, 9, 15, 15, 8, 8, 7, 7},{12, 10, 17, 16, 23, 23, 25, 25},{11, 18, 18, 19, 19, 27, 28, 26},{20, 20, 21, 21, 22, 24, 29, 29},{13, 40, 40, 42, 42, 33, 33, 32},{39, 39, 41, 43, 43, 34, 34, 30},{14, 38, 37, 37, 36, 35, 31, 31}},
{{9, 10, 1, 16, 2, 3, 4, 5, 6},{11, 10, 15, 16, 8, 3, 7, 26, 6},{11, 12, 17, 19, 22, 24, 23, 26, 25},{13, 12, 17, 18, 22, 24, 27, 28, 29},{13, 40, 20, 41, 21, 33, 27, 28, 30},{14, 38, 39, 41, 36, 42, 35, 32, 30},{14, 38, 37, 43, 36, 34, 35, 32, 31}}
};
ANS[8][8][0] = {
{{1, 2, 2, 3, 4, 5, 8, 8},{10, 10, 9, 6, 6, 7, 7, 16},{11, 17, 17, 22, 21, 20, 18, 18},{12, 12, 23, 23, 24, 24, 19, 25},{31, 31, 33, 33, 34, 35, 26, 26},{13, 32, 37, 37, 36, 36, 27, 27},{39, 40, 40, 38, 45, 46, 28, 28},{14, 41, 41, 43, 43, 48, 48, 29},{15, 15, 42, 44, 44, 47, 47, 30}},
{{11, 1, 10, 2, 3, 4, 5, 7, 8},{11, 1, 9, 6, 3, 4, 5, 19, 16},{12, 17, 9, 22, 21, 20, 18, 19, 16},{13, 32, 23, 22, 21, 20, 24, 25, 26},{13, 32, 31, 38, 33, 34, 35, 25, 27},{14, 40, 37, 38, 36, 34, 35, 29, 28},{14, 39, 42, 43, 45, 48, 46, 29, 30},{15, 39, 42, 41, 45, 44, 46, 47, 30}}
};
ANS[9][8][0] = {
{{1, 1, 2, 3, 4, 6, 8, 8},{9, 9, 10, 5, 5, 7, 7, 21},{13, 11, 14, 14, 15, 15, 22, 22},{12, 29, 32, 32, 36, 36, 23, 23},{30, 31, 31, 33, 38, 37, 24, 24},{16, 34, 34, 39, 39, 41, 41, 25},{17, 17, 35, 35, 44, 44, 40, 26},{18, 18, 54, 51, 51, 43, 27, 27},{19, 48, 50, 50, 47, 47, 45, 42},{20, 49, 49, 53, 52, 46, 46, 28}},
{{9, 11, 1, 2, 3, 4, 6, 7, 8},{12, 11, 10, 2, 3, 5, 6, 21, 22},{12, 13, 10, 33, 14, 37, 15, 21, 23},{16, 13, 29, 33, 32, 37, 36, 25, 24},{16, 30, 29, 31, 38, 39, 40, 25, 26},{17, 30, 35, 34, 38, 43, 40, 41, 26},{18, 19, 48, 51, 44, 43, 45, 42, 27},{20, 19, 48, 54, 53, 52, 45, 42, 28},{20, 49, 50, 54, 53, 52, 47, 46, 28}}
};
ANS[10][8][0] = {
{{1, 4, 5, 5, 6, 7, 8, 8},{2, 3, 10, 11, 11, 9, 9, 12},{21, 21, 17, 17, 18, 14, 14, 13},{23, 24, 20, 20, 16, 16, 15, 15},{22, 26, 26, 19, 38, 38, 42, 42},{27, 28, 25, 37, 37, 44, 41, 46},{29, 29, 36, 36, 43, 47, 47, 45},{31, 35, 35, 48, 49, 49, 51, 51},{30, 39, 39, 57, 57, 59, 59, 50},{33, 33, 40, 58, 58, 60, 53, 53},{32, 34, 34, 56, 55, 55, 54, 52}},
{{1, 3, 4, 11, 5, 6, 7, 9, 8},{1, 2, 4, 10, 17, 6, 7, 14, 12},{21, 22, 20, 10, 19, 18, 16, 13, 12},{23, 22, 24, 25, 19, 18, 41, 13, 15},{23, 26, 24, 25, 38, 43, 41, 45, 42},{29, 27, 28, 37, 36, 43, 44, 45, 46},{30, 27, 28, 35, 49, 47, 44, 50, 46},{30, 31, 40, 39, 48, 57, 60, 50, 51},{32, 31, 40, 56, 48, 59, 60, 54, 52},{32, 34, 33, 56, 55, 58, 53, 54, 52}}
};
ANS[1][9][0] = {
{{1, 10, 10, 9, 9, 8, 8, 7, 7},{2, 2, 3, 3, 4, 4, 5, 5, 6}},
{{1, 10, 2, 9, 3, 8, 4, 7, 5, 6}}
};
ANS[2][9][0] = {
{{1, 1, 5, 10, 12, 12, 14, 14, 15},{4, 3, 3, 11, 11, 13, 13, 16, 16},{2, 2, 6, 6, 7, 7, 8, 9, 9}},
{{1, 3, 5, 10, 12, 13, 14, 8, 15, 16},{2, 4, 5, 10, 6, 11, 7, 8, 15, 9}}
};
ANS[3][9][0] = {
{{1, 2, 3, 6, 6, 7, 7, 8, 8},{4, 4, 5, 5, 14, 14, 20, 20, 21},{10, 10, 12, 12, 15, 15, 19, 22, 22},{9, 11, 11, 13, 13, 16, 17, 18, 18}},
{{4, 1, 2, 3, 5, 6, 19, 7, 20, 8},{9, 1, 2, 3, 14, 16, 19, 17, 21, 22},{9, 11, 10, 13, 12, 16, 15, 17, 21, 18}}
};
ANS[4][9][0] = {
{{1, 2, 3, 3, 4, 4, 5, 5, 6},{8, 8, 10, 11, 11, 13, 13, 12, 12},{7, 15, 16, 16, 24, 24, 28, 26, 26},{14, 17, 17, 20, 20, 25, 29, 29, 27},{9, 18, 18, 19, 21, 21, 22, 22, 23}},
{{7, 1, 2, 11, 3, 13, 4, 12, 5, 6},{7, 14, 8, 10, 16, 25, 24, 26, 27, 6},{9, 14, 15, 10, 19, 25, 29, 28, 27, 23},{9, 17, 15, 18, 19, 20, 21, 28, 22, 23}}
};
ANS[5][9][0] = {
{{1, 1, 6, 7, 8, 8, 9, 10, 10},{3, 5, 5, 13, 13, 34, 31, 31, 29},{4, 2, 12, 14, 14, 35, 35, 30, 30},{15, 15, 11, 21, 21, 33, 33, 32, 28},{17, 17, 19, 19, 22, 23, 23, 27, 27},{16, 18, 18, 20, 20, 24, 25, 26, 26}},
{{1, 2, 6, 5, 7, 13, 8, 9, 31, 10},{3, 2, 11, 14, 7, 35, 34, 9, 32, 29},{3, 4, 11, 12, 22, 33, 34, 30, 32, 29},{16, 4, 15, 12, 22, 21, 24, 25, 28, 27},{16, 18, 17, 20, 19, 23, 24, 25, 28, 26}}
};
ANS[6][9][0] = {
{{1, 2, 2, 3, 3, 4, 4, 5, 5},{7, 7, 8, 8, 13, 13, 38, 37, 35},{6, 17, 18, 18, 12, 14, 14, 39, 36},{9, 9, 19, 23, 23, 40, 40, 34, 34},{16, 15, 22, 22, 24, 31, 41, 41, 33},{10, 20, 20, 25, 25, 30, 30, 32, 32},{11, 11, 21, 26, 27, 28, 28, 29, 29}},
{{6, 1, 8, 2, 12, 3, 13, 4, 36, 5},{6, 1, 7, 19, 12, 14, 38, 37, 36, 35},{9, 16, 17, 19, 18, 24, 38, 37, 39, 35},{10, 16, 17, 23, 22, 24, 41, 40, 39, 34},{10, 15, 21, 20, 26, 27, 31, 30, 33, 32},{11, 15, 21, 25, 26, 27, 31, 28, 33, 29}}
};
ANS[7][9][0] = {
{{1, 1, 2, 3, 4, 5, 5, 6, 6},{14, 15, 15, 19, 19, 20, 21, 21, 23},{7, 17, 17, 25, 25, 26, 26, 22, 24},{8, 8, 16, 28, 27, 42, 42, 41, 41},{9, 9, 29, 30, 30, 45, 44, 44, 47},{10, 13, 18, 34, 34, 43, 46, 48, 48},{11, 31, 31, 35, 35, 39, 39, 40, 40},{12, 12, 32, 33, 36, 36, 37, 37, 38}},
{{7, 15, 1, 2, 3, 4, 21, 5, 22, 6},{7, 14, 16, 19, 27, 4, 20, 26, 22, 23},{8, 14, 16, 17, 27, 25, 20, 42, 24, 23},{9, 10, 18, 30, 28, 43, 44, 46, 24, 41},{11, 10, 18, 29, 28, 43, 45, 46, 47, 48},{11, 13, 32, 29, 33, 34, 45, 39, 47, 38},{12, 13, 32, 31, 33, 35, 36, 40, 37, 38}}
};
ANS[8][9][0] = {
{{1, 3, 3, 29, 31, 31, 33, 33, 34},{2, 2, 4, 30, 30, 32, 32, 35, 35},{6, 6, 28, 27, 52, 53, 53, 38, 38},{8, 5, 13, 13, 51, 51, 54, 37, 40},{7, 12, 12, 26, 50, 50, 48, 48, 39},{11, 11, 17, 17, 36, 36, 47, 41, 41},{9, 14, 14, 18, 18, 49, 43, 43, 44},{15, 15, 19, 19, 23, 23, 46, 45, 42},{10, 16, 20, 21, 22, 24, 24, 25, 25}},
{{1, 3, 4, 28, 29, 32, 31, 35, 33, 34},{1, 5, 2, 28, 29, 30, 54, 38, 37, 34},{7, 5, 6, 27, 51, 52, 54, 53, 37, 39},{7, 8, 13, 27, 50, 52, 48, 47, 40, 39},{9, 8, 11, 12, 26, 49, 36, 47, 40, 41},{9, 14, 17, 18, 26, 49, 46, 45, 43, 42},{10, 16, 15, 20, 21, 22, 46, 45, 44, 42},{10, 16, 19, 20, 21, 22, 23, 24, 44, 25}}
};
ANS[9][9][0] = {
{{1, 2, 2, 3, 3, 4, 5, 5, 6},{7, 7, 14, 14, 17, 16, 16, 15, 15},{8, 8, 9, 19, 20, 20, 25, 25, 27},{22, 22, 18, 23, 24, 24, 28, 28, 26},{10, 21, 30, 30, 32, 33, 29, 54, 54},{36, 36, 34, 34, 31, 57, 57, 56, 53},{11, 35, 40, 40, 46, 46, 59, 59, 55},{38, 37, 37, 39, 45, 58, 60, 60, 52},{12, 41, 41, 43, 43, 49, 49, 51, 51},{13, 13, 42, 44, 44, 47, 48, 50, 50}},
{{7, 1, 9, 2, 14, 3, 4, 16, 5, 6},{8, 1, 9, 18, 20, 17, 4, 15, 26, 6},{10, 21, 22, 18, 19, 17, 25, 29, 26, 27},{10, 21, 30, 23, 19, 31, 24, 29, 28, 27},{11, 35, 34, 23, 32, 31, 33, 57, 55, 54},{11, 35, 36, 39, 32, 58, 33, 56, 55, 53},{12, 37, 40, 39, 46, 58, 59, 56, 60, 53},{12, 38, 42, 43, 45, 49, 47, 48, 52, 51},{13, 38, 42, 41, 45, 44, 47, 48, 52, 50}}
};
ANS[10][9][0] = {
{{1, 1, 2, 3, 4, 5, 5, 6, 7},{9, 9, 10, 8, 8, 19, 19, 20, 20},{11, 22, 22, 25, 25, 26, 21, 62, 57},{12, 23, 23, 30, 30, 49, 49, 63, 63},{13, 13, 28, 28, 29, 48, 66, 66, 56},{24, 27, 39, 37, 37, 61, 67, 64, 64},{14, 31, 36, 36, 38, 47, 47, 65, 55},{15, 15, 35, 35, 41, 41, 58, 60, 60},{16, 16, 33, 40, 40, 45, 45, 59, 53},{17, 34, 34, 42, 44, 44, 50, 52, 52},{18, 32, 32, 43, 43, 46, 51, 51, 54}},
{{9, 11, 1, 2, 3, 4, 21, 5, 6, 7},{12, 11, 10, 8, 3, 4, 21, 19, 6, 20},{12, 23, 10, 22, 29, 25, 26, 63, 62, 57},{13, 24, 28, 30, 29, 49, 26, 67, 62, 57},{14, 24, 31, 37, 38, 48, 66, 67, 65, 56},{14, 27, 31, 39, 38, 48, 61, 64, 65, 56},{15, 27, 36, 39, 41, 47, 61, 60, 59, 55},{16, 17, 35, 40, 42, 45, 50, 58, 59, 55},{18, 17, 33, 34, 42, 46, 50, 58, 54, 53},{18, 32, 33, 43, 44, 46, 51, 52, 54, 53}}
};
ANS[1][10][0] = {
{{1, 2, 2, 3, 3, 4, 4, 5, 5, 6},{11, 11, 10, 10, 9, 9, 8, 8, 7, 7}},
{{11, 1, 10, 2, 9, 3, 8, 4, 7, 5, 6}}
};
ANS[2][10][0] = {
{{1, 1, 2, 3, 3, 4, 4, 5, 6, 6},{7, 7, 11, 11, 18, 18, 15, 15, 12, 12},{9, 8, 10, 10, 17, 16, 16, 14, 14, 13}},
{{7, 8, 1, 2, 11, 3, 15, 4, 5, 13, 6},{9, 8, 10, 2, 17, 16, 18, 14, 5, 13, 12}}
};
ANS[3][10][0] = {
{{1, 2, 3, 4, 5, 8, 8, 9, 10, 10},{11, 11, 6, 6, 7, 7, 19, 22, 24, 24},{12, 14, 14, 16, 16, 18, 18, 23, 23, 25},{13, 13, 15, 15, 17, 17, 20, 20, 21, 21}},
{{1, 12, 2, 3, 4, 5, 7, 8, 9, 25, 10},{11, 12, 6, 3, 4, 5, 19, 22, 9, 25, 24},{13, 14, 15, 16, 17, 18, 19, 22, 20, 23, 21}}
};
ANS[4][10][0] = {
{{1, 3, 3, 6, 6, 22, 22, 30, 31, 31},{2, 4, 5, 5, 21, 21, 23, 23, 32, 32},{9, 8, 8, 7, 25, 26, 26, 29, 29, 28},{10, 10, 13, 13, 24, 24, 20, 18, 18, 27},{11, 11, 12, 14, 15, 15, 16, 17, 19, 19}},
{{1, 3, 5, 6, 7, 22, 21, 30, 31, 28, 32},{1, 2, 4, 8, 7, 26, 20, 30, 23, 28, 27},{10, 9, 12, 14, 24, 25, 20, 16, 17, 29, 27},{11, 9, 12, 14, 13, 25, 15, 16, 17, 18, 19}}
};
ANS[5][10][0] = {
{{1, 2, 2, 3, 4, 5, 5, 6, 7, 7},{8, 8, 10, 10, 13, 14, 15, 15, 18, 19},{9, 9, 22, 22, 16, 16, 20, 21, 21, 17},{25, 24, 24, 23, 34, 33, 33, 32, 32, 38},{11, 26, 27, 27, 35, 35, 36, 36, 39, 39},{12, 12, 28, 29, 29, 30, 30, 31, 37, 37}},
{{8, 1, 10, 2, 3, 4, 15, 5, 6, 17, 7},{9, 1, 22, 23, 3, 13, 14, 21, 18, 17, 19},{11, 24, 26, 23, 16, 13, 14, 20, 18, 32, 19},{11, 25, 26, 28, 34, 33, 35, 20, 31, 38, 39},{12, 25, 27, 28, 34, 29, 36, 30, 31, 38, 37}}
};
ANS[6][10][0] = {
{{1, 2, 3, 4, 5, 5, 6, 6, 7, 8},{15, 14, 14, 13, 13, 11, 11, 10, 9, 9},{16, 16, 18, 18, 12, 38, 38, 39, 40, 40},{17, 23, 23, 32, 32, 41, 37, 43, 45, 45},{19, 19, 34, 33, 33, 42, 42, 44, 44, 46},{21, 21, 29, 35, 36, 36, 31, 31, 30, 30},{20, 22, 24, 24, 25, 26, 26, 27, 27, 28}},
{{1, 14, 2, 3, 4, 12, 5, 11, 6, 7, 8},{15, 17, 2, 13, 4, 12, 37, 10, 9, 7, 8},{15, 17, 16, 32, 18, 38, 37, 10, 39, 46, 40},{19, 23, 29, 33, 35, 42, 41, 43, 39, 46, 45},{20, 22, 29, 34, 35, 25, 41, 43, 30, 44, 28},{20, 22, 21, 34, 24, 25, 36, 26, 31, 27, 28}}
};
ANS[7][10][0] = {
{{1, 2, 3, 3, 4, 4, 5, 5, 6, 7},{22, 22, 21, 18, 18, 14, 14, 10, 8, 8},{47, 49, 49, 19, 16, 16, 17, 9, 11, 12},{48, 50, 50, 51, 20, 24, 15, 15, 13, 13},{46, 46, 53, 53, 23, 25, 25, 26, 26, 27},{45, 45, 52, 42, 39, 39, 32, 32, 28, 28},{44, 43, 43, 41, 41, 40, 33, 33, 29, 29},{38, 38, 37, 36, 36, 35, 35, 34, 31, 30}},
{{1, 2, 3, 19, 4, 14, 5, 9, 8, 6, 7},{22, 48, 21, 19, 20, 18, 16, 9, 10, 6, 7},{47, 48, 21, 49, 20, 23, 15, 17, 10, 11, 12},{47, 50, 52, 51, 53, 23, 24, 17, 13, 11, 12},{46, 44, 52, 51, 39, 40, 24, 25, 28, 26, 27},{45, 44, 37, 41, 42, 40, 32, 34, 31, 30, 27},{38, 43, 37, 36, 42, 35, 33, 34, 31, 30, 29}}
};
ANS[8][10][0] = {
{{1, 3, 5, 5, 6, 6, 7, 8, 9, 9},{2, 4, 4, 22, 20, 20, 11, 10, 10, 12},{25, 25, 24, 24, 21, 16, 16, 15, 14, 14},{26, 26, 47, 47, 23, 40, 39, 38, 38, 13},{29, 27, 49, 46, 46, 41, 41, 42, 37, 37},{28, 48, 50, 50, 45, 45, 44, 43, 43, 17},{30, 30, 51, 60, 60, 58, 56, 56, 35, 36},{32, 32, 52, 52, 59, 57, 57, 55, 55, 18},{31, 33, 34, 34, 53, 53, 54, 54, 19, 19}},
{{1, 3, 5, 4, 20, 21, 6, 7, 8, 10, 9},{1, 2, 25, 22, 23, 21, 11, 7, 8, 12, 13},{26, 27, 24, 22, 23, 16, 11, 15, 14, 12, 13},{28, 27, 48, 46, 47, 40, 39, 15, 37, 38, 17},{28, 29, 48, 49, 45, 40, 39, 41, 42, 36, 17},{30, 29, 50, 49, 59, 60, 44, 43, 42, 36, 18},{31, 33, 32, 51, 59, 58, 44, 57, 56, 35, 18},{31, 33, 34, 51, 52, 58, 53, 55, 54, 35, 19}}
};
ANS[9][10][0] = {
{{1, 2, 2, 3, 4, 5, 5, 6, 6, 7},{16, 17, 17, 18, 19, 19, 22, 22, 21, 21},{8, 20, 24, 25, 25, 29, 30, 30, 36, 36},{23, 26, 28, 28, 32, 32, 31, 38, 35, 39},{9, 27, 27, 33, 33, 34, 34, 37, 40, 40},{10, 10, 65, 65, 58, 58, 59, 45, 45, 44},{11, 11, 66, 66, 64, 54, 54, 46, 47, 41},{14, 12, 67, 63, 63, 62, 53, 53, 42, 42},{13, 57, 57, 60, 61, 61, 51, 51, 48, 48},{15, 15, 56, 55, 55, 52, 52, 50, 49, 43}},
{{8, 1, 20, 2, 3, 4, 19, 5, 22, 6, 7},{8, 16, 20, 17, 18, 4, 30, 31, 21, 35, 7},{9, 16, 28, 24, 18, 25, 29, 31, 37, 35, 36},{9, 23, 26, 24, 32, 34, 29, 38, 37, 39, 40},{10, 23, 26, 27, 64, 33, 58, 38, 46, 39, 41},{11, 12, 65, 67, 64, 62, 59, 45, 46, 44, 41},{13, 12, 66, 67, 60, 62, 59, 54, 47, 44, 42},{13, 14, 56, 57, 60, 63, 53, 50, 47, 49, 43},{15, 14, 56, 55, 61, 52, 51, 50, 48, 49, 43}}
};
ANS[10][10][0] = {
{{1, 2, 3, 3, 4, 5, 11, 11, 13, 13},{9, 8, 8, 7, 6, 6, 10, 10, 15, 15},{29, 30, 30, 33, 33, 34, 35, 12, 14, 17},{32, 31, 38, 37, 37, 36, 36, 16, 18, 18},{39, 40, 40, 42, 41, 48, 49, 28, 28, 19},{43, 44, 44, 45, 45, 47, 47, 50, 27, 27},{46, 46, 55, 54, 53, 53, 52, 51, 51, 20},{59, 56, 56, 65, 65, 66, 66, 25, 25, 26},{61, 61, 67, 71, 71, 73, 57, 57, 24, 21},{60, 63, 63, 72, 74, 74, 68, 68, 22, 22},{62, 62, 64, 64, 70, 70, 69, 58, 23, 23}},
{{1, 2, 3, 8, 4, 5, 10, 12, 11, 14, 13},{9, 30, 31, 7, 4, 5, 6, 12, 16, 14, 15},{9, 29, 31, 7, 41, 33, 34, 35, 16, 19, 17},{32, 29, 38, 37, 41, 36, 34, 35, 18, 19, 17},{32, 39, 38, 40, 42, 47, 48, 49, 27, 28, 20},{43, 39, 46, 44, 42, 45, 48, 49, 50, 26, 20},{43, 56, 55, 54, 53, 65, 52, 51, 50, 26, 21},{60, 59, 55, 54, 72, 71, 52, 66, 57, 25, 21},{60, 59, 61, 67, 72, 73, 74, 69, 58, 24, 22},{62, 63, 64, 67, 70, 73, 68, 69, 58, 24, 23}}
};
ANS[4][6][1] = {
{{0, 0, 0, 0, 0, 0},{7, 7, 12, 16, 16, 14},{8, 9, 9, 13, 15, 6},{2, 2, 11, 11, 10, 10},{1, 3, 3, 4, 4, 5}},
{{0, 8, 7, 13, 15, 16, 6},{0, 8, 12, 13, 15, 14, 6},{0, 1, 12, 9, 11, 14, 5},{0, 1, 2, 3, 10, 4, 5}}
};
ANS[6][6][1] = {
{{0, 0, 0, 0, 0, 0},{11, 11, 23, 24, 19, 19},{12, 13, 13, 21, 20, 4},{10, 10, 22, 22, 5, 5},{9, 8, 15, 15, 18, 17},{7, 7, 14, 16, 16, 6},{1, 1, 2, 2, 3, 3}},
{{0, 12, 11, 21, 19, 20, 4},{0, 12, 23, 21, 24, 20, 4},{0, 9, 23, 13, 24, 18, 5},{0, 9, 10, 14, 22, 18, 6},{0, 8, 7, 14, 15, 17, 6},{0, 8, 1, 16, 2, 17, 3}}
};
ANS[7][6][1] = {
{{0, 0, 0, 0, 0, 0},{23, 23, 25, 25, 5, 5},{22, 24, 26, 27, 13, 6},{21, 21, 28, 28, 19, 7},{18, 18, 20, 20, 14, 15},{11, 17, 17, 16, 16, 8},{9, 9, 10, 10, 12, 12},{1, 1, 2, 3, 3, 4}},
{{0, 24, 25, 26, 13, 6, 5},{0, 24, 23, 26, 13, 6, 7},{0, 22, 21, 27, 28, 14, 7},{0, 22, 20, 27, 19, 14, 8},{0, 17, 18, 16, 19, 15, 8},{0, 11, 9, 2, 10, 15, 4},{0, 11, 1, 2, 12, 3, 4}}
};
ANS[6][4][1] = {
{{0, 0, 0, 0},{16, 16, 3, 3},{15, 14, 14, 4},{12, 12, 13, 5},{8, 8, 10, 11},{7, 9, 9, 6},{1, 1, 2, 2}},
{{0, 15, 16, 4, 3},{0, 15, 13, 4, 5},{0, 14, 13, 11, 5},{0, 7, 12, 11, 6},{0, 7, 8, 10, 6},{0, 9, 1, 10, 2}}
};
ANS[6][6][1] = {
{{0, 0, 0, 0, 0, 0},{16, 16, 13, 13, 12, 12},{15, 19, 19, 14, 11, 5},{17, 17, 18, 24, 24, 22},{9, 20, 20, 21, 23, 6},{7, 7, 8, 8, 10, 10},{1, 1, 2, 3, 3, 4}},
{{0, 15, 16, 14, 13, 11, 5},{0, 15, 18, 14, 12, 11, 5},{0, 19, 18, 21, 23, 24, 6},{0, 20, 17, 21, 23, 22, 6},{0, 9, 7, 2, 10, 22, 4},{0, 9, 1, 2, 8, 3, 4}}
};
ANS[6][7][1] = {
{{0, 0, 0, 0, 0, 0, 0},{23, 23, 21, 21, 20, 14, 14},{25, 24, 22, 19, 19, 13, 9},{26, 26, 28, 18, 18, 15, 15},{12, 27, 27, 17, 17, 16, 10},{11, 11, 8, 8, 7, 6, 6},{1, 1, 2, 3, 3, 4, 5}},
{{0, 24, 23, 22, 21, 14, 13, 9},{0, 24, 28, 22, 20, 19, 13, 9},{0, 25, 28, 18, 20, 15, 16, 10},{0, 25, 26, 27, 7, 17, 16, 10},{0, 12, 11, 2, 7, 6, 4, 5},{0, 12, 1, 2, 8, 3, 4, 5}}
};
ANS[4][6][2] = {
{{0, 0, 0, 0, 0, 0},{16, 18, 18, 4, 4, 2},{1, 17, 15, 5, 3, 3},{14, 14, 11, 11, 6, 8},{13, 12, 12, 10, 9, 7}},
{{1, 18, 17, 15, 5, 4, 2},{1, 16, 17, 15, 5, 6, 3},{13, 16, 11, 10, 9, 6, 7},{13, 12, 14, 10, 9, 8, 7}}
};
ANS[5][6][2] = {
{{0, 0, 0, 0, 0, 0},{1, 4, 4, 14, 14, 15},{3, 3, 5, 9, 13, 2},{6, 12, 21, 20, 20, 16},{7, 17, 18, 18, 19, 10},{8, 8, 22, 22, 11, 11}},
{{1, 4, 5, 9, 13, 14, 2},{3, 6, 5, 9, 13, 15, 2},{7, 6, 17, 20, 19, 15, 10},{7, 12, 17, 21, 19, 16, 10},{8, 12, 18, 21, 22, 16, 11}}
};
ANS[6][6][2] = {
{{0, 0, 0, 0, 0, 0},{1, 1, 13, 13, 12, 12},{2, 10, 18, 14, 11, 4},{3, 20, 20, 19, 5, 5},{21, 22, 22, 17, 16, 15},{6, 23, 23, 25, 25, 8},{7, 7, 24, 26, 9, 9}},
{{1, 2, 10, 14, 13, 11, 4},{3, 2, 10, 14, 12, 11, 4},{3, 21, 18, 20, 17, 15, 5},{6, 21, 18, 19, 17, 15, 8},{6, 22, 24, 19, 26, 16, 8},{7, 23, 24, 25, 26, 16, 9}}
};
ANS[7][6][2] = {
{{0, 0, 0, 0, 0, 0},{13, 13, 18, 15, 15, 2},{1, 14, 17, 16, 20, 20},{4, 4, 22, 23, 19, 3},{11, 10, 21, 25, 25, 24},{5, 9, 31, 27, 27, 6},{7, 7, 29, 29, 26, 26},{8, 8, 30, 28, 28, 12}},
{{1, 14, 13, 17, 16, 15, 2},{1, 14, 18, 17, 16, 19, 3},{4, 11, 18, 21, 20, 19, 3},{5, 11, 22, 21, 23, 25, 6},{5, 10, 22, 27, 23, 24, 6},{7, 9, 30, 31, 26, 24, 12},{8, 9, 30, 31, 29, 28, 12}}
};
ANS[6][4][2] = {
{{0, 0, 0, 0},{1, 1, 4, 4},{2, 5, 6, 8},{3, 10, 10, 7},{9, 9, 11, 15},{12, 17, 17, 14},{13, 18, 16, 16}},
{{1, 2, 5, 6, 4},{3, 2, 5, 6, 7},{3, 10, 11, 8, 7},{9, 12, 11, 8, 14},{13, 12, 18, 15, 14},{13, 17, 18, 15, 16}}
};
ANS[6][5][2] = {
{{0, 0, 0, 0, 0},{1, 1, 22, 22, 20},{4, 2, 5, 21, 6},{3, 18, 18, 7, 7},{12, 17, 19, 19, 15},{8, 14, 14, 16, 10},{9, 9, 13, 11, 11}},
{{1, 2, 5, 21, 22, 6},{3, 2, 5, 21, 20, 6},{3, 4, 17, 18, 20, 7},{8, 4, 17, 16, 19, 10},{8, 12, 13, 16, 15, 10},{9, 12, 13, 14, 15, 11}}
};
ANS[6][6][2] = {
{{0, 0, 0, 0, 0, 0},{13, 13, 14, 14, 2, 2},{1, 12, 15, 6, 3, 5},{17, 16, 16, 25, 25, 4},{7, 18, 26, 26, 24, 11},{19, 19, 23, 22, 22, 8},{10, 20, 20, 21, 9, 9}},
{{1, 12, 14, 15, 6, 3, 2},{1, 12, 13, 15, 6, 3, 4},{7, 16, 18, 25, 24, 5, 4},{7, 17, 18, 23, 24, 5, 8},{10, 17, 26, 23, 21, 11, 8},{10, 20, 19, 22, 21, 11, 9}}
};
ANS[6][7][2] = {
{{0, 0, 0, 0, 0, 0, 0},{11, 10, 10, 14, 14, 2, 2},{1, 13, 12, 18, 15, 16, 3},{5, 5, 17, 26, 26, 25, 4},{19, 20, 20, 28, 29, 29, 24},{6, 21, 21, 27, 30, 30, 8},{7, 7, 22, 23, 23, 9, 9}},
{{1, 10, 12, 14, 15, 16, 3, 2},{1, 11, 12, 17, 15, 16, 3, 4},{5, 11, 13, 17, 18, 26, 24, 4},{6, 20, 13, 27, 18, 25, 24, 8},{6, 19, 22, 27, 28, 25, 29, 8},{7, 19, 22, 21, 28, 23, 30, 9}}
};
ANS[4][6][3] = {
{{1, 3, 3, 4, 5, 5},{2, 2, 10, 10, 15, 15},{8, 9, 9, 13, 16, 17},{7, 7, 12, 12, 18, 18},{6, 6, 11, 11, 14, 14}},
{{0, 1, 2, 3, 4, 16, 5},{0, 1, 10, 9, 4, 16, 15},{0, 8, 7, 13, 12, 17, 18},{0, 8, 6, 13, 11, 17, 14}}
};
ANS[5][6][3] = {
{{1, 1, 2, 2, 3, 3},{8, 8, 10, 10, 12, 12},{9, 22, 22, 11, 15, 13},{21, 21, 18, 18, 14, 14},{20, 19, 19, 17, 16, 16},{4, 4, 5, 6, 6, 7}},
{{0, 9, 1, 11, 2, 13, 3},{0, 9, 8, 11, 10, 13, 12},{0, 20, 21, 22, 17, 15, 14},{0, 20, 18, 5, 17, 15, 7},{0, 19, 4, 5, 16, 6, 7}}
};
ANS[6][6][3] = {
{{1, 1, 2, 3, 4, 4},{10, 12, 12, 5, 5, 13},{11, 11, 16, 16, 14, 14},{17, 17, 18, 18, 15, 20},{25, 24, 24, 19, 22, 22},{26, 26, 23, 23, 21, 21},{6, 6, 7, 8, 8, 9}},
{{0, 12, 1, 2, 3, 5, 4},{0, 10, 11, 2, 3, 15, 13},{0, 10, 16, 19, 14, 15, 13},{0, 24, 17, 19, 18, 20, 22},{0, 25, 26, 7, 23, 20, 9},{0, 25, 6, 7, 21, 8, 9}}
};
ANS[7][6][3] = {
{{1, 3, 3, 5, 6, 6},{2, 2, 4, 4, 14, 14},{7, 9, 9, 30, 30, 15},{8, 8, 27, 27, 29, 29},{18, 18, 23, 23, 28, 16},{21, 22, 22, 26, 17, 17},{19, 19, 20, 20, 25, 24},
{10, 10, 11, 12, 12, 13}},
{{0, 1, 4, 3, 5, 15, 6},{0, 1, 2, 9, 5, 15, 14},{0, 7, 8, 30, 29, 28, 16},{0, 7, 18, 26, 27, 28, 16},{0, 22, 23, 26, 25, 24, 17},{0, 21, 19, 11, 25, 24, 13},{0, 21, 10, 11, 20, 12, 13}}
};
ANS[6][4][3] = {
{{1, 2, 6, 6},{3, 5, 5, 7},{4, 4, 11, 11},{8, 8, 12, 12},{18, 18, 13, 15},{17, 16, 16, 14},{9, 9, 10, 10}},
{{0, 1, 2, 7, 6},{0, 3, 2, 5, 11},{0, 3, 4, 13, 12},{0, 17, 8, 13, 14},{0, 17, 18, 15, 14},{0, 16, 9, 15, 10}}
};
ANS[6][5][3] = {
{{1, 2, 6, 6, 7},{3, 5, 5, 8, 8},{4, 4, 13, 13, 14},{9, 9, 19, 19, 20},{15, 15, 22, 21, 21},{16, 17, 17, 18, 18},{10, 10, 11, 11, 12}},
{{0, 1, 2, 8, 6, 7},{0, 3, 2, 5, 13, 7},{0, 3, 4, 22, 19, 14},{0, 16, 9, 22, 20, 14},{0, 16, 15, 21, 20, 12},{0, 17, 10, 18, 11, 12}}
};
ANS[6][6][3] = {
{{1, 3, 3, 5, 5, 6},{2, 2, 4, 4, 11, 11},{7, 9, 9, 10, 10, 21},{8, 8, 15, 12, 22, 20},{14, 14, 25, 25, 23, 23},{16, 16, 26, 26, 24, 24},{13, 17, 17, 18, 18, 19}},  {{0, 1, 4, 3, 11, 5, 6},{0, 1, 2, 10, 12, 20, 6},{0, 7, 8, 9, 12, 20, 21},{0, 7, 14, 15, 23, 22, 21},{0, 13, 25, 15, 24, 22, 19},{0, 13, 16, 17, 26, 18, 19}}
};
ANS[6][7][3] = {
{{1, 3, 3, 4, 5, 6, 7},{2, 2, 10, 9, 9, 8, 8},{11, 12, 12, 19, 19, 21, 21},{13, 13, 18, 18, 20, 30, 30},{14, 17, 17, 24, 28, 28, 31},{16, 16, 23, 23, 27, 29, 29},
{15, 15, 22, 22, 25, 25, 26}},
{{0, 1, 2, 3, 4, 5, 6, 7},{0, 1, 10, 9, 20, 8, 6, 7},{0, 11, 10, 12, 20, 19, 31, 21},{0, 11, 13, 17, 18, 27, 31, 30},{0, 14, 16, 24, 23, 27, 28, 26},{0, 14, 15, 24, 22, 29, 25, 26}}
};
ANS[9][6][3] = {
  {{1, 3, 3, 4, 5, 5}, {2, 2, 11, 12, 12, 13}, {10, 10, 16, 16, 15, 15}, {23, 25, 25, 37, 38, 14}, {24, 24, 34, 34, 35, 35}, {26, 26, 33, 36, 36, 17}, {28, 28, 32, 32, 18, 18}, {29, 30, 27, 27, 19, 19}, {31, 31, 22, 22, 21, 20}, {6, 6, 7, 8, 8, 9}},
  {{0, 1, 2, 3, 4, 12, 5}, {0, 1, 10, 11, 4, 13, 14}, {0, 25, 16, 11, 15, 13, 14}, {0, 23, 24, 37, 35, 38, 17}, {0, 23, 26, 37, 34, 38, 17}, {0, 29, 28, 33, 32, 36, 18},
{0, 29, 27, 33, 21, 20, 19}, {0, 30, 31, 7, 21, 20, 9}, {0, 30, 6, 7, 22, 8, 9}}
};
ANS[6][9][2] = {
  {{0, 0, 0, 0, 0, 0, 0, 0, 0}, {15, 14, 14, 20, 20, 22, 22, 2, 2}, {1, 17, 16, 18, 19, 21, 6, 3, 5}, {7, 7, 26, 26, 28, 28, 30, 30, 4}, {8, 8, 25, 27, 36, 29, 33, 31, 13}, {9, 24, 24, 38, 38, 32, 34, 34, 11}, {10, 23, 23, 37, 37, 35, 35, 12, 12}},
  {{1, 14, 16, 18, 19, 20, 21, 6, 3, 2}, {1, 15, 16, 18, 19, 22, 21, 6, 3, 4}, {7, 15, 17, 27, 28, 29, 30, 31, 5, 4}, {8, 9, 17, 27, 26, 29, 32, 31, 5, 11}, {10, 9, 25, 24, 36, 38, 32, 33, 13, 11}, {10, 23, 25, 37, 36, 35, 34, 33, 13, 12}}
};
}

int tms = 0;
void bar(int dx, int dy, int x, int y){
    // cout << " " << 0 << " " << dx << " " << dy << "\n";
    ++tms;
    auto baz = ANS[dx][dy][0];
    int lx = x - dx;
    int ly = y - dy;
    FOR(i, lx, x)
        FOR(j, ly, y - 1)
            cc[i][j] = baz.a[i - lx][j - ly] + tms * 200;
    FOR(i, lx, x - 1)
        FOR(j, ly, y)
            sq[i][j] = baz.b[i - lx][j - ly] + tms * 200;
    return ;
}
void foo(int dx, int dy, int x, int y){
    // cout << " " << 1 << " " << dx << " " << dy << "\n";
    ++tms;
    auto baz = ANS[dx][dy][1];
    int lx = x - dx;
    int ly = y - dy;
    FOR(i, lx, x)
        FOR(j, ly, y - 1)
            cc[i][j] = baz.a[i - lx][j - ly] + tms * 200;
    FOR(i, lx, x - 1)
        FOR(j, ly, y)
            sq[i][j] = baz.b[i - lx][j - ly] + tms * 200;
    return ;
}
void bar2(int dx, int dy, int x, int y){
    // cout << " " << 2 << " " << dx << " " << dy << "\n";
    ++tms;
    auto baz = ANS[dx][dy][2];
    int lx = x - dx;
    int ly = y - dy;
    FOR(i, lx, x)
        FOR(j, ly, y - 1)
            cc[i][j] = baz.a[i - lx][j - ly] + tms * 200;
    FOR(i, lx, x - 1)
        FOR(j, ly, y)
            sq[i][j] = baz.b[i - lx][j - ly] + tms * 200;
    return ;
}
void bar3(int dx, int dy, int x, int y){
    // cout << " " << 3 << " " << dx << " " << dy << "\n";
    ++tms;
    auto baz = ANS[dx][dy][3];
    int lx = x - dx;
    int ly = y - dy;
    FOR(i, lx, x)
        FOR(j, ly, y - 1)
            cc[i][j] = baz.a[i - lx][j - ly] + tms * 200;
    FOR(i, lx, x - 1)
        FOR(j, ly, y)
            sq[i][j] = baz.b[i - lx][j - ly] + tms * 200;
    return ;
}

void output(){
    n = nn, m = mm;
    // FOR(i, 0, n) FOR(j, 0, m - 1) cout << cc[i][j] << " \n"[j == m - 1];
    // FOR(i, 0, n - 1) FOR(j, 0, m) cout << sq[i][j] << " \n"[j == m];

    vector<tuple<int, int, int> > out;
    FOR(i, 0, n) FOR(j, 0, m){
        vector<int> type;
        if(cc[i][j] == cc[i][j + 1] && cc[i][j] == sq[i][j]) type.pb(1);
        else if(cc[i][j] == sq[i][j] && cc[i][j] == sq[i + 1][j]) type.pb(2);
        else if(cc[i][j] == sq[i][j]) type.pb(0);
        if(i >= 2 && cc[i][j] == sq[i - 1][j] && cc[i][j] == sq[i - 2][j]) type.pb(4);
        else if(i >= 1 && cc[i][j] == sq[i - 1][j] && cc[i][j] == cc[i][j + 1]) type.pb(5);
        else if(i >= 1 && cc[i][j] == sq[i - 1][j]) type.pb(3);
        if(i >= 1 && j >= 2 && cc[i][j - 1] == cc[i][j - 2] && cc[i][j - 1] == sq[i - 1][j]) type.pb(7);
        else if(i >= 2 && j >= 1 && cc[i][j - 1] == sq[i - 1][j] && cc[i][j - 1] == sq[i - 2][j]) type.pb(8);
        else if(i >= 1 && j >= 1 && cc[i][j - 1] == sq[i - 1][j]) type.pb(6);
        if(j >= 1 && cc[i][j - 1] == sq[i][j] && sq[i][j] == sq[i + 1][j]) type.pb(10);
        else if(j >= 2 && cc[i][j - 1] == sq[i][j] && sq[i][j] == cc[i][j - 2]) type.pb(11);
        else if(j >= 1 && cc[i][j - 1] == sq[i][j]) type.pb(9);
        for(auto x : type) out.push_back(make_tuple(i, j, x));
    }
    cout << out.size() << "\n";
    for(auto i : out)
        cout << get<1>(i) << " " << get<0>(i) << " " << get<2>(i) << "\n";
    return ;
}

void solve(){
    cin >> n >> m;
    swap(n, m); nn = n, mm = m;
    cc = vector<vector<int> >(n + 5, vector<int>(m + 5, 0));
    sq = vector<vector<int> >(n + 5, vector<int>(m + 5, 0));
    int randomnoise = 1e9;
    FOR(i, 0, n + 3) FOR(j, 0, m + 3) cc[i][j] = ++randomnoise, sq[i][j] = ++randomnoise;

    while(m > 10 && n >= 6){
        int top = n;
        while(top){
            int flg = 0;
            if(top == 6) bar3(6, 6, top, m);
            else if(top == 7) bar3(7, 6, top, m);
            else if(top == 8) foo(4, 6, top, m), bar3(4, 6, top - 4, m);
            else if(top == 9) bar3(9, 6, top, m);
            else if(top == 10) foo(6, 6, top, m), bar3(4, 6, top - 6, m);
            else if(top == 11) foo(7, 6, top, m), bar3(4, 6, top - 7, m);
            else foo(6, 6, top, m), top -= 6, flg = 1;
            if(!flg) break;
        }
        m -= 6;
    }
    while(n > 10 && m >= 6){
        int top = m;
        while(top){
            int flg = 0;
            if(top == 6) bar2(6, 6, n, top);
            else if(top == 7) bar2(6, 7, n, top);
            else if(top == 8) foo(6, 4, n, top), bar2(6, 4, n, top - 4);
            else if(top == 9) bar2(6, 9, n, top);
            else if(top == 10) foo(6, 6, n, top), bar2(6, 4, n, top - 6);
            else if(top == 11) foo(6, 7, n, top), bar2(6, 4, n, top - 7);
            else foo(6, 6, n, top), top -= 6, flg = 1;
            if(!flg) break;
        }
        n -= 6;
    }

    if(n == 4 && m > 10){
        while(m > 10){
            bar3(4, 6, n, m);
            m -= 6;
        }
    }
    if(n == 5 && m > 10){
        while(m > 10){
            bar3(5, 6, n, m);
            m -= 6;
        }
    }
    if(n > 10 && m == 4){
        while(n > 10){
            bar2(6, 4, n, m);
            n -= 6;
        }
    }
    if(n > 10 && m == 5){
        while(n > 10){
            bar2(6, 5, n, m);
            n -= 6;
        }
    }

    if(n <= 10 && m <= 10){
        bar(n, m, n, m);
        output();
        return ;
    }

    if(n == 1){
        int idx = (++tms) * 200;
        cc[0][0] = sq[0][0] = ++idx;
        for(int i = 2; i < m; i += 2) cc[0][i] = cc[0][i - 1] = sq[0][i - 1] = ++idx;
        for(int i = 1; i < m; i += 2) cc[1][i] = cc[1][i - 1] = sq[0][i + 1] = ++idx;
        if(m & 1) sq[0][m] = cc[1][m - 1] = ++idx;
        else cc[0][m - 1] = sq[0][m - 1] = ++idx;
        output();
        return ;
    }
    if(m == 1){
        int idx = (++tms) * 200;
        cc[0][0] = sq[0][1] = ++idx;
        for(int i = 2; i <= n; i += 2) sq[i - 2][0] = sq[i - 1][0] = cc[i][0] = ++idx;
        for(int i = 2; i < n; i += 2) sq[i][1] = sq[i - 1][1] = cc[i - 1][0] = ++idx;
        if(n & 1) sq[n - 1][0] = cc[n][0] = ++idx;
        else sq[n - 1][1] = cc[n - 1][0] = ++idx;
        output();
        return ;
    }

    int swapflg = 0;
    if(m == 2){
        swap(n, m);
        swapflg = 1;
    }
    if(n == 2){
        int dx[] = {0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4};
        int dy[] = {0, -1, 0, -1, 0, 1, -1, 0, -1, 0, 1, -1, 0};

        int idx = (++tms) * 200;
        int nowP = m, nowS = 1453;

        vector<vector<int>> pic = vector<vector<int> >(2 * n + 5, vector<int>(2 * m + 5, 1e9));
        while(!(nowP == 1 && nowS == 0)){
            int from = 0;
            if(nowP <= 40) from = fr[nowP][iuf[nowS]];
            else from = fr[nowP % 4 + 40][iuf[nowS]];
            if(from < 1000){
                ++idx;
                for(auto i : puzzles[from]) pic[dx[i]][dy[i] + nowP] = idx;
                for(auto i : puzzles[from]) nowS ^= (1 << (i - 1));
            }
            else{
                ++idx;
                for(auto i : puzzles[from - 1000]) pic[dx[i]][dy[i] + nowP - 1] = idx;
                nowP--;
                int a[13];
                FOR(k, 1, 12) a[k] = (bool)(nowS & (1 << (k - 1)));
                int b[13] = {0, 1, a[1], 1, a[3], a[4], 1, a[6], 1, a[8], a[9], 1, a[11]};
                for(auto i : puzzles[from - 1000]) b[i] = 0;
                nowS = 0;
                FOR(k, 1, 12) nowS |= (b[k] << (k - 1));
            }
        }

        if(!swapflg){
            FOR(i, 0, n) FOR(j, 0, m - 1) cc[i][j] = pic[2 * i][j];
            FOR(i, 0, n - 1) FOR(j, 0, m) sq[i][j] = pic[2 * i + 1][j];
        }
        else{
            swap(n, m);
            FOR(i, 0, n) FOR(j, 0, m - 1) cc[i][j] = pic[2 * j + 1][i];
            FOR(i, 0, n - 1) FOR(j, 0, m) sq[i][j] = pic[2 * j][i];
        }
        output();
        return ;
    }

    if(m == 3){
        swap(n, m);
        swapflg = 1;
    }
    if(n == 3){
        int dx[] = {0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 5, 5, 5, 6, 6};
        int dy[] = {0, -1, 0, -1, 0, 1, -1, 0, -1, 0, 1, -1, 0, -1, 0, 1, -1, 0};

        int idx = (++tms) * 200;
        int nowP = m, nowS = 46509;

        vector<vector<int>> pic = vector<vector<int> >(2 * n + 5, vector<int>(2 * m + 5, 1e9));
        while(!(nowP == 1 && nowS == 0)){
            int from = 0;
            if(nowP <= 24) from = fr3[nowP][iuf3[nowS]];
            else from = fr3[24 + nowP % 6][iuf3[nowS]];
            if(from < 1000){
                ++idx;
                for(auto i : puzzles3[from]) pic[dx[i]][dy[i] + nowP] = idx;
                for(auto i : puzzles3[from]) nowS ^= (1 << (i - 1));
            }
            else{
                ++idx;
                for(auto i : puzzles3[from - 1000]) pic[dx[i]][dy[i] + nowP - 1] = idx;
                nowP--;
                int a[18];
                FOR(k, 1, 17) a[k] = (bool)(nowS & (1 << (k - 1)));
                int b[18] = {0, 1, a[1], 1, a[3], a[4], 1, a[6], 1, a[8], a[9], 1, a[11], 1, a[13], a[14], 1, a[16]};
                for(auto i : puzzles3[from - 1000]) b[i] = 0;
                nowS = 0;
                FOR(k, 1, 17) nowS |= (b[k] << (k - 1));
            }
        }

        if(!swapflg){
            FOR(i, 0, n) FOR(j, 0, m - 1) cc[i][j] = pic[2 * i][j];
            FOR(i, 0, n - 1) FOR(j, 0, m) sq[i][j] = pic[2 * i + 1][j];
        }
        else{
            swap(n, m);
            FOR(i, 0, n) FOR(j, 0, m - 1) cc[i][j] = pic[2 * j + 1][i];
            FOR(i, 0, n - 1) FOR(j, 0, m) sq[i][j] = pic[2 * j][i];
        }
        output();
        return ;
    }
    cout << "WRONG!\n"; exit(0);
    return ;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    init();

    FOR(i, 0, useful.size() - 1) iuf[useful[i]] = i;
    dp[1][iuf[0]] = 0;

    FOR(i, 1, M - 1){
        for(auto j : useful) if(dp[i][iuf[j]] < 1e9){
            int a[13], b[13];
            FOR(k, 1, 12) a[k] = (bool)(j & (1 << (k - 1))), b[k] = a[k];
            for(int K = 0; K < puzzles.size(); K++){
                auto k = puzzles[K];
                int flg = 0; for(int tmp : k) flg |= (b[tmp] == 1); if(flg) continue;
                for(int tmp : k) b[tmp] = 1;

                if(b[1] && b[3] && b[6] && b[8] && b[11]){
                    int c[] = {0, b[2], 0, b[4], b[5], 0, b[7], 0, b[9], b[10], 0, b[12], 0}, C = 0;
                    FOR(tmp, 1, 12) C |= (c[tmp] << (tmp - 1));
                    if(iuf[C] != 1e9){
                        if(dp[i + 1][iuf[C]] > dp[i][iuf[j]] + 3 - k.size()){
                            dp[i + 1][iuf[C]] = dp[i][iuf[j]] + 3 - k.size();
                            fr[i + 1][iuf[C]] = 1000 + K;
                        }
                    }
                }
                else{
                    int B = 0;
                    FOR(tmp, 1, 12) B |= (b[tmp] << (tmp - 1));
                    if(iuf[B] != 1e9){
                        if(dp[i][iuf[B]] > dp[i][iuf[j]] + 3 - k.size()){
                            dp[i][iuf[B]] = dp[i][iuf[j]] + 3 - k.size();
                            fr[i][iuf[B]] = K;
                        }
                    }
                }

                for(int tmp : k) b[tmp] = 0;
            }
        }
    }

    FOR(i, 0, useful3.size() - 1) iuf3[useful3[i]] = i;
    dp3[1][iuf[0]] = 0;

    FOR(i, 1, M - 1){
        for(auto j : useful3) if(dp3[i][iuf3[j]] < 1e9){
            int a[18], b[18];
            FOR(k, 1, 17) a[k] = (bool)(j & (1 << (k - 1))), b[k] = a[k];
            for(int K = 0; K < puzzles3.size(); K++){
                auto k = puzzles3[K];
                int flg = 0; for(int tmp : k) flg |= (b[tmp] == 1); if(flg) continue;
                for(int tmp : k) b[tmp] = 1;

                if(b[1] && b[3] && b[6] && b[8] && b[11] && b[13] && b[16]){
                    int c[] = {0, b[2], 0, b[4], b[5], 0, b[7], 0, b[9], b[10], 0, b[12], 0, b[14], b[15], 0, b[17], 0}, C = 0;
                    FOR(tmp, 1, 17) C |= (c[tmp] << (tmp - 1));
                    if(iuf3[C] != 1e9){
                        if(dp3[i + 1][iuf3[C]] > dp3[i][iuf3[j]] + 3 - k.size()){
                            dp3[i + 1][iuf3[C]] = dp3[i][iuf3[j]] + 3 - k.size();
                            fr3[i + 1][iuf3[C]] = 1000 + K;
                        }
                    }
                }
                else{
                    int B = 0;
                    FOR(tmp, 1, 17) B |= (b[tmp] << (tmp - 1));
                    if(iuf3[B] != 1e9){
                        if(dp3[i][iuf3[B]] > dp3[i][iuf3[j]] + 3 - k.size()){
                            dp3[i][iuf3[B]] = dp3[i][iuf3[j]] + 3 - k.size();
                            fr3[i][iuf3[B]] = K;
                        }
                    }
                }

                for(int tmp : k) b[tmp] = 0;
            }
        }
    }

    int T; cin >> T;
    while(T--) solve();
    return 0;
}

Comments

No comments yet.
العربية English 日本語 简体中文 繁體中文

Made with ❤️ by Qingyu✨

服务器时间: 2026-03-23 06:17:38