This page is still under construction.

Parts of this page are still being built. What you see may change.

Cube

Time limit2sMemory limit1024 MB

Summary
Decide whether six numbered cells in a 6 by 6 grid fold into a cube and report the face opposite face 1.
Level

Medium6 of 10

Topics
Simulation, BFS, Matrix
Solved
No attempts yet

Problem

Six squares joined edge to edge in the right pattern can be folded into a cube. The six squares on the left below fold into a cube, and there face 1 is opposite face 4, face 2 is opposite face 6, and face 3 is opposite face 5. The six squares on the right do not fold into a cube, because faces 3 and 5 land on the same face.

A 6 × 6 array holds the six squares. Only 6 of the 36 cells hold a square, and each of those cells contains the number of that square. Every other cell contains 0. One figure has many representations, because it can sit anywhere in the array and in any orientation. Rotating the whole array by 90 degrees turns one representation into another.

If the six squares are not joined edge to edge into a single piece, they cannot be folded into a cube.

Given one array, decide whether the squares fold into a cube, and if they do, find the face opposite face 1.

Input

The input has six lines, and each line has six integers. All but six of the integers are 0. The six non-zero integers are 1, 2, 3, 4, 5, 6.

Output

Print a single integer. Print 0 if the squares cannot be folded into a cube. Otherwise print the number of the face opposite face 1.

Examples3

  1. Example 1

    Input
    0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 0 0
0 5 2 3 0 0
0 0 4 0 0 0
0 0 6 0 0 0
    Expected output
    4

  2. Example 2

    Input
    0 0 0 0 0 0
0 3 0 5 0 0
1 2 4 6 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
    Expected output
    0

  3. Example 3

    Input
    0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 5 6
0 0 0 0 0 4
0 0 0 0 3 2
0 0 0 0 0 1
    Expected output
    0