Background

Translated from Problem M of NERC 2018.

Problem Description

Marika is making a game called Minegraphed. In this game, you move inside a three-dimensional rectangular cuboid. Each cell of the cuboid is either an empty cell or an obstacle cell. You are always in an empty cell, either on the bottom layer, or on top of an obstacle. For each move, you can choose one of the four directions: east, south, west, or north. The moving rules are as follows:

• You cannot move outside the cuboid.
• If the cell in front of you is empty, then you can move forward by one cell, and then fall down until you reach the bottom layer or land on an obstacle.
• If you are not on the top layer, the cell in front of you is an obstacle, and the cell above you and the cell above that obstacle are both empty, then you can climb onto the top of that obstacle.
• In all other cases, you cannot move.

There are $n$ special empty cells that you can stand on in the cuboid, numbered from $1$ to $n$.

Marika also has a $n \times n$ 2D array $a$, which is the adjacency matrix of a directed graph with $n$ vertices ($a_{i,j}=1$ means there is an edge $i\to j$, and vice versa). You need to make it so that vertex $i$ can reach vertex $j$ by following some directed edges if and only if, in the cuboid game field, it is possible to reach the cell numbered $j$ starting from the cell numbered $i$ by performing moves.

Please construct a valid arrangement.

Input Format

The first line contains an integer $n \ (1 \leq n \leq 9)$.

Then follow $n$ lines, each containing $n$ numbers $a_{i,1},a_{i,2},\ldots,a_{i,n}$, representing the adjacency matrix of the directed graph.

Output Format

Output the first line with $x,y,z$, representing the length, width, and height of your cuboid. You must ensure that $x \times y \times z \leq 10^6$.

Then output $z$ layers (from top to bottom). Each layer is an $x \times y$ rectangle: if $map_{i,j}$ is #, it means an obstacle; if it is ., it means a normal empty cell; if it is a digit, it means a special empty cell, and the digit is its corresponding index.

It is guaranteed that a solution exists.

4
0 1 0 1
0 0 1 0
0 1 0 0
1 0 0 0

4 2 3
..#.
.4..
####
1#.#
..3.
#2..

Hint

Explanation of the sample:

For all testdata, it is guaranteed that $1 \leq n \leq 9$ and $a_{i,j} \in \{0, 1\}$.

Translated by ChatGPT 5