#P2147. Dice Puzzle

Dice Puzzle

本题没有可用的提交语言。

描述

让我们尝试一个骰子拼图。这个谜题的规则如下:

  1. 拼图中使用了图66所示的六个面的骰子。
  2. 2727个这样的骰子,可以构建一个3×3×33 \times 3 \times 3的立方体,如图77所示。
  3. 当构建一个由骰子组成的立方体时,相邻骰子面上标记的数字之和必须为77(见图88)。例如,如果对中的一个面标记为"2""2",则另一个面必须标记为"5""5"
  4. 给出了立方体的顶视图和前视图的一部分,即给出了顶部和正面的一些骰子面上的数字(见图99)。
  5. 拼图的目标是找到与给定的顶视图和前视图信息一致的所有合理的骰子排列。

你的工作是编写一个程序来解决这个难题。

输入

输入由以下格式的多个数据集组成: N 数据集1 数据集2 ... 数据集N

NN是数据集的数量。

每个数据集的格式如下: T11 T12 T13 T21 T22 T23 T31 T32 T33 F11 F12 F13 F21 F22 F23 F31 F32 F33

TijTijFijFij1i31 \leq i \leq 31j31 \leq j \leq 3)是出现在顶视图和前视图上的骰子面,如图77所示,或者是一个零。零表示相应位置的人脸未知。

输出

对于每个可能的骰子排列,计算出现在立方体右侧的九个面上标记的数字之和,即使用图771i31j3Rij\sum_{1 \leq i \leq 3}\sum_{1 \leq j \leq 3}Rij

对于每个数据集,你应该以升序且不重复的方式输出所有合理排列的右侧视图和。数字之间用单个空格分隔。当数据集没有合理的排列时,输出一个零。

例如,假设顶视图和前视图如图1010所示。有44个合理的右视图,如图1111所示。右侧视图总和分别为3333363632323333。将它们重新排列成升序并消除重复项后,答案应该是"32 33 36""32\ 33\ 36"

输出应为每个数据集提供一行。

输入数据 1

4
1 1 1
1 1 1
1 1 1
2 2 2
2 2 2
2 2 2
4 3 3
5 2 2
4 3 3
6 1 1
6 1 1
6 1 0
1 0 0
0 2 0
0 0 0
5 1 2
5 1 2
0 0 0
2 0 0
0 3 0
0 0 0
0 0 0
0 0 0
3 0 1

输出数据 1

27 24 32 33 36 0

日本20042004