ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

USU Championship 2003

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Unicube

Time limit: 1.0 second
Memory limit: 64 MB
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.

Input

The first line consists of one number 0 < N < 31 — the number of toy-bricks in the set. 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 — the total number of toy-bricks in the figure to be built (0 < M < 31). 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 — a cell coordinates (all of them from 0 to 30), F, U, R, D, L, B — demand 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 is accepted the left coordinate system (e.g. OX axis looks right, OY — straight and OZ — up) — this is natural for Vasya building the figure on the floor.

Output

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.

Sample

inputoutput
1
6 1 3 4 5 2
1
0 0 0 1 2 3 6 5 4
1
Problem Author: Alexander Mironenko
Problem Source: Ural State University championship, October 25, 2003
To submit the solution for this problem go to the Problem set: 1270. Unicube