Kreegan's attack in 1165 (Xeen's chronology) was one of the hardest challenges
in the history of Enroth.
However, the artifacts found after this war lead to the intense development
of magic in Enroth.
The way some of these artifacts work is still unknown,
and the best mages conduct serious research and experiments
trying to perceive their magic power.
One of these artifacts is a magic cube which, according to veterans
of that war, was used by kreegans to prolong the spells' action,
thus saving the power of mages.
This cube consists of many erudin crystals which are small cubes
of equal size.
Some faces of these crystals are covered with runes.
Adjacent faces of two neighboring crystals contain the same rune on them.
Faces that don't contain a rune on them form the faces of the whole
Unfortunately, now this artifact is disassembled and is represented
by the set of crystals.
Previous attempts to connect them were unsuccessful as the cube
constantly broke into pieces during the process.
However, the scientists discovered that the relative positions of certain
pairs of crystals in the assembled cube play a great role in its magic power.
Now the researchers want to analyze the runes on the faces of crystals
to restore the way the cube should be assembled, and to calculate
the distance between some pairs of crystals in the assembled cube.
Crystals can be rotated and moved arbitrarily.
The first line contains integers l and n which are the length of edge
of a single crystal and the ratio of artifact edge's length to crystal
edge's length (1 ≤ l ≤ 100; 2 ≤ n ≤ 30).
The following n3 lines describe crystals.
Each line contains six numbers in range from 0 to 109
which denote the numbers of runes on the faces of a crystal
according to the list of kreegan's runes by Patvin Darkenmore.
Number 0 means that the face doesn't have a rune on it.
Faces are described in the following order:
bottom, top, right, left, front, back.
It is guaranteed that any positive rune number
is present exactly twice in the description of all crystals.
The next line contains an integer m which is the number of pairs of crystals
researchers want to investigate (1 ≤ m ≤ 10 000).
Each of the following m lines contains integers a and b, which are
the numbers of crystals you should find a distance between
(1 ≤ a < b ≤ n3).
Crystals are numbered in the order they are described in input.
For each pair of crystals, output on a single line a distance between the
centers of these crystals in the assembled artifact.
Absolute or relative error should not exceed 10−6.
0 8 73 0 0 16
0 9 0 73 0 1000
0 146 4 0 16 0
0 15 0 4 1000 0
146 0 1 0 6 0
15 0 0 1 2 0
8 0 17 0 0 6
9 0 0 17 0 2
Problem Author: Mikhail Rubinchik (prepared by Denis Mukhametianov)
Problem Source: Ural SU Team.GOV Contest. Petrozavodsk Summer Session, August 2011