Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3467
3D Knight Moves

Time Limit: 10 Seconds      Memory Limit: 65536 KB

Tradisional knight move can be described by (1, 2). 3D knight move is described by (x, y, z). So it can move in 48 different ways totally. Your job is to write a program that takes two coordinates and (x, y, z) as input and then determines the number of 3D knight moves on a shortest route from one to another.

Fig 1 shows all 8 possible tradisional knight moves of (1, 2). Fig 2 demonstrates a way of 3D knight move (2, 3, 4).

Input

The input file will contain one or more test cases. Each test case consists of two lines. The first line contains 6 integers that are coordinates of the two points (x0, y0, z0) and (x1, y1, z1). The second line contains 3 integers (x, y, z) that describe the 3D knight move. ( -1000 < x0, y0, z0, x1, y1, z1 < 1000; 0 < x < y < z < 1000 )

Output

For each test case, first print one line saying "To get from (x0,y0,z0) to (x1,y1,z1) takes n 3D knight moves (x,y,z): ", then print the lexicographically minimum route which is made up by n + 1 points, if n is not larger than 6; print "To get from (x0,y0,z0) to (x1,y1,z1) takes more than 6 3D knight moves (x,y,z)." otherwise. See sample for more details.

Sample Input

0 0 0 3 2 1
1 2 3
0 0 0 -9 -3 -6
1 2 3
0 0 0 3 6 8
1 2 3

Sample Output

To get from (0,0,0) to (3,2,1) takes 1 3D knight moves (1,2,3): (0,0,0) => (3,2,1).
To get from (0,0,0) to (-9,-3,-6) takes 3 3D knight moves (1,2,3): (0,0,0) => (-3,-1,-2) => (-6,-2,-4) => (-9,-3,-6).
To get from (0,0,0) to (3,6,8) takes more than 6 3D knight moves (1,2,3).

Author: GAO, Yuan
Contest: ZOJ Monthly, February 2011
Submit    Status