5520. 「PA 2019 Final」Pionki

题目描述

题目译自 PA 2019 Final Pionki

给定一个三维棋盘，由尺寸为 $A \times B \times C$ 的长方体中的立方体单元格组成。每个单元格可以用一组数字 $(i, j, k)$ 表示，其中 $1 \leq i \leq A$，$1 \leq j \leq B$，$1 \leq k \leq C$。对于每个单元格，我们知道其初始包含的棋子数量，单元格 $(i, j, k)$ 中有 $a_{i, j, k}$ 个棋子。在一次移动中，你可以选择一个至少包含一个棋子的单元格，并将其中的一个棋子移动到相邻的单元格 $(i+1, j, k)$、$(i, j+1, k)$ 或 $(i, j, k+1)$，前提是目标单元格存在。

对于每个单元格，我们还知道一个目标值 $b_{i, j, k}$。你的任务是判断是否可以通过一系列移动（可能是零次移动），使得每个单元格 $(i, j, k)$ 中的棋子数量正好为 $b_{i, j, k}$。

输入格式

输入数据的第一行包含一个整数 $t$ $(1 \leq t \leq 10000)$，表示测试数据的数量。

接下来是 $t$ 组测试数据的描述。每组测试数据以一行开始，包含三个整数 $A, B, C$ $(1 \leq A \leq 10000, 1 \leq B, C \leq 6)$，表示棋盘的尺寸。接着是 $A$ 个块，每个块包含 $B$ 行。每行包含 $C$ 个整数，第 $i$ 个块的第 $j$ 行的第 $k$ 个数字是 $a_{i, j, k}$ $(0 \leq a_{i, j, k} \leq 10^{12})$。随后，以相同格式给出目标值 $b_{i, j, k}$ $(0 \leq b_{i, j, k} \leq 10^{12})$。

每组测试数据总共包含 $2 \cdot A$ 个块。为提高可读性，相邻块之间用空行分隔。在每组测试数据中，$a_{i, j, k}$ 的总和等于 $b_{i, j, k}$ 的总和。

所有测试数据的 $A$ 值总和不超过 $10000$。

输出格式

输出应包含恰好 $t$ 行，如果在第 $z$ 组测试数据中可以执行一系列移动从初始状态到达目标状态，在第 $z$ 行输出 TAK，否则输出 NIE。

样例

输入

2
2 3 4
2 0 0 1
0 0 1 0
1 0 0 0

0 1 0 0
1 0 0 0
0 0 0 0

0 0 1 0
0 1 0 0
0 0 0 0

1 0 0 0
0 0 0 0
0 0 0 4
2 2 2
2 2
2 1

2 1
1 1

1 1
1 2

1 2
2 2

输出

NIE
TAK

第二组测试数据中，以下是从初始状态到目标状态的一系列移动：