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

Ural SU Team.GOV contest. Petrozavodsk training camp. Summer 2011

About     Problems     Submit solution     Judge status     Standings
Contest is over

H. Magic Cube

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

Input

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 < bn3). Crystals are numbered in the order they are described in input.

Output

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.

Sample

inputoutput
1 2
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
2
1 5
2 8
1.4142135
1
Problem Author: Mikhail Rubinchik (prepared by Denis Mukhametianov)
Problem Source: Ural SU Team.GOV Contest. Petrozavodsk Summer Session, August 2011
To submit the solution for this problem go to the Problem set: 1858. Magic Cube