Snake Cube#5305
The snake cube is a mechanical puzzle made up of n^3 cubes, each measuring 1 \times 1 \times 1, connected by an elastic cord. Each pair of adjacent cubes on the cord touches at one face and can rotate freely around an axis perpendicular to that face. Every three consecutive cubes form either a straight line or a degree angle. You cannot bend a straight segment of the snake into an angle or straighten an angle into a straight segment; you can only decide, through rotations, which of the four directions the snake turns at each angle. The objective is to assemble a larger cube of size n \times n \times n using this snake. An example of a snake is shown in the figure.
Not every snake can be assembled into a cube; at a minimum, all straight sections of the snake must consist of no more than cubes.
We define the snake by the sequence of lengths of its straight segments, specifically by the sequence of distances between the centers of the first and last cubes in each straight segment. For example, the snake shown in the figure is defined from left to right as follows: 2~1~1~2~1~2~1~1~2~2~1~1~1~2~2~2~2.
In this task, you are asked to solve a generalized version of this puzzle. A snake with l \times w \times h cells is given. Fit it into a rectangular parallelepiped of size l \times w \times h cells or determine that it is impossible.
The first line contains four integers , , , (1 \leq l, w, h \leq 4;~0 \leq m < lwh), where , , and are the length, width, and height of the parallelepiped, respectively, and is the number of segments in the snake. The second line contains positive integers—the sequence of lengths of the straight segments of the snake. It is guaranteed that the given snake contains exactly l \times w \times h cubes.
If it is impossible to fit the given snake into the parallelepiped, output "Bit" on the first line. Otherwise, output "Baba" on the first line, and in the next l \times w \times h lines output the coordinates of the snake's cubes in order, three numbers per line. The snake should be output starting from the same end as in the input file. The numbers x_i, y_i, z_i in the (i+1)-th line must satisfy 0 \leq x_i < l, 0 \leq y_i < w, 0 \leq z_i < h. Every cube in the parallelepiped must appear exactly once in the output, adjacent lines must contain adjacent cubes, and the turns must precisely match the snake's configuration. The snake can start and end in any cube of the parallelepiped. If multiple solutions exist, output any of them.
Example 1