Unicube is a remarkable set of toy-bricks developed by B. P. Nikitin especially for the children. Vasya’s dad made such a set to his son. Nothing special — a set of 27 colored toy-bricks — each edge is colored red, blue or yellow. But the coloring allows to build the cube 3×3×3 with outer surface of any of the colors. Moreover, it allows (but not easily) to build a 3×3×3 cube with chess coloring not only of the outer edges, but of all the 6 (and taking into account two sides of each section, all the 12) sections of the cube. In short this toy is for the children up to 10 years and Vasya played it with his father.
When they had built all the figures suggested in the book (which could be built) Vasya began to bother his father with the question if it was possible to build such-and-such a figure with such-and-such a coloring. At first father tried to build Vasya’s figures. Sometimes he succeeded and sometimes not. At the end father made a request to the students of the Ural State University to automate his distressing toil. Of course, the students equipped with computers would easily implement his request.
Your task is to write a program that given n information about the set of toy-bricks and the figure that is to be built, would suggest how to arrange the toy-bricks in order to build the figure. All the figures in the problem are the located in the three-dimensional space cells cubes such that some of the edges must be of a definite color.
The first line consists of one integer N that is the number of toy-bricks in the set (1 ≤ N ≤ 30). Then there are N lines with the toy-bricks description: for each toy-brick in the order “front, upper, right, lower, left, back” pointed out the color of the edge number (integer from 1 to 30). Then in a new line there is an integer M that is the total number of toy-bricks in the figure to be built (1 ≤ M ≤ 30). At last there are M lines with the figure description in the following format: <X> <Y> <Z> <F> <U> <R> <D> <L> <B>, where X, Y, Z are coordinates of the cell (all of them are from 0 to 30), F, U, R, D, L, B are demands to the colors of the toy-brick in this cell in the same order as in description of the available toy-bricks colors (from 1 to 30; if there is 0 then there might be an arbitrary color). Here we use the left coordinate system (e.g. OX axis looks right, OY looks forward and OZ looks up) which is natural for Vasya building the figure on the floor.
If there is at least one solution of the problem then your program is to output an arbitrary solution in the form of M lines. The i-th line is to contain the number of toy-brick (in the order given in the input starting from 1) for a cell number i (in the same order as in the input starting from 1). If there is no solution, then you are to output 0.
6 1 3 4 5 2
0 0 0 1 2 3 6 5 4
Problem Author: Alexander Mironenko
Problem Source: Ural State University championship, October 25, 2003