Wise Beads Puzzle

The Wise Beads Puzzle consists of a triangular board (the board piece) and 12 distinct pieces made up of connected beads. Each piece can be rotated by 0°, 90°, 180°, or 270° and can be flipped horizontally or vertically. Given an initial layout of the board, where each cell is marked with a 0 (available) or 1 (already occupied), your task is to determine whether there exists a feasible placement for all 12 pieces on the board. All pieces must be placed without overlapping and must fit within the available spaces of the board. It is guaranteed that in all test cases a solution exists.

If a valid placement exists, simply output Solution exists. Otherwise, output -1 (though for this problem, all test cases guarantee a solution exists).

Note: The board is triangular. The first line of the input gives an integer R representing the number of rows. The first row has 1 cell, the second row has 2 cells, and so on. Each subsequent row contains the appropriate number of integers separated by spaces.

Example:

Input:
3
0
0 0
0 0 0
Output:
Solution exists

inputFormat

The input begins with an integer R (1 ≤ R ≤ 10) denoting the number of rows of the triangular board. The following R lines describe the board layout. The i-th line contains i space-separated integers. Each integer is either 0 (indicating an empty cell where a piece may be placed) or 1 (indicating that the cell is occupied or blocked).

For example:

3
0
0 0
0 0 0

outputFormat

Output a single line displaying Solution exists if all 12 pieces can be placed onto the board according to the rules. Otherwise, output -1. For this problem, you may assume that the provided board will always allow a valid placement, so the correct output in all cases is Solution exists.

sample

3
0
0 0
0 0 0

Solution exists