Dice Puzzle

Time limit1sMemory limit128 MB

Summary
Given partial top and front faces of a 3x3x3 cube of standard dice with fixed chirality and opposite-face contact constraints, enumerate all valid orientations and report every possible sum of the right-side faces.
Level

Medium7 of 10

Topics
Backtracking, Simulation, Combinatorics, Brute force
Solved
No attempts yet

Problem

You are given the following dice puzzle.

  1. Every die is an ordinary six-sided die whose opposite faces always sum to 77 (so 11 is opposite 66, 22 is opposite 55, and 33 is opposite 44). Every die has the same right-handed orientation: when the face showing 11 is on top and the face showing 22 is at the front, the face showing 33 is on the right.
  2. Twenty-seven such dice are packed together to form a 3×3×33 \times 3 \times 3 cube.
  3. Wherever two dice touch, the two faces pressed against each other must sum to 77. For example, if one face of a touching pair shows 22, the face it is pressed against shows 55.
  4. Some of the die faces that appear on the top and on the front of the cube are given; every other face is unknown.
  5. A plausible arrangement is any way of placing and orienting the 2727 dice that obeys all of the rules above and matches every given top and front face.

For each plausible arrangement, look at the right side of the cube and add the nine numbers that appear there. Your task is to report every possible value of this right-side sum.

Input

The first line contains an integer NN, the number of datasets. The NN datasets follow.

Each dataset consists of six lines. The first three lines describe the top view of the cube as a 3×33 \times 3 grid

T11 T12 T13
T21 T22 T23
T31 T32 T33

and the next three lines describe the front view as a 3×33 \times 3 grid in the same layout

F11 F12 F13
F21 F22 F23
F31 F32 F33

Each TijT_{ij} and FijF_{ij} is either the number on that face (an integer from 11 to 66) or 00, which means the face is unknown. The values in a line are separated by spaces.

Number the columns of both grids 11 to 33 from left to right. The cube splits into three vertical layers, one per column, and the jj-th column of the top view and the jj-th column of the front view describe the same layer. Such a layer holds nine dice, indexed by depth (front to back) and by height (bottom to top). The three entries of that top-view column list the layer's top faces, one per depth; the three entries of that front-view column list the layer's front faces, one per height. Consequently the die at a given depth and height in the layer shows the top face of that depth and the front face of that height.

Output

For each dataset, consider every plausible arrangement and compute, for each of them, the sum of the nine faces RijR_{ij} on the right side of the cube (numbered like the other views), that is ∑i=13∑j=13Rij\sum_{i=1}^{3}\sum_{j=1}^{3} R_{ij}.

Print one line per dataset containing all the distinct right-side sums in ascending order, separated by a single space. If the dataset has no plausible arrangement, print a single 00. The output is compared exactly, so do not print any trailing spaces at the end of a line.

Examples1

  1. Example 1

    Input
    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
    
    Expected output
    27
    24
    32 33 36
    0