Problem 1095 --Coincidance

1095: Coincidance

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 32  Solved: 13
[Submit][Status][Web Board][Creator:]

Description

宇宙级偶像 KiKi 和 Choo − Choo 都热爱跳抖肩舞,为了将抖肩舞带来地球上的 HHU,他们踏上了旅 途: 

假设整个宇宙被描述为一个三维的立方体,范围为 (x, y, z), 0 ≤ x ≤ n, 0 ≤ y ≤ m, 0 ≤ z ≤ k. 

KiKi 和 Choo − Choo 在坐标 (sx, sy, sz) 处,HHU 在 (gx, gy, gz) 处,太空中有若干个长方体 (形) 状 的粉丝团,每个粉丝团的范围为 (x, y, z), ai1 ≤ x ≤ ai2 , bi1 ≤ y ≤ bi2 , ci1 ≤ z ≤ ci2

当 KiKi 和 Choo − Choo 接触粉丝团时,热情的粉丝会拦下 KiKi 和 Choo − Choo 索要签名,这使得 KiKi 和 Choo − Choo 不能再前进 (不能再到 HHU)。 

KiKi 和 Choo − Choo 每秒只能从上下左右前后六个方向中选择一个方向走一个单位,作为迎接他们的 HHUer,请你计算一下,KiKi 和 Choo − Choo 到 HHU 最快要多久呢?

Input

第 1 行,3 个整数 n, m, k(1 ≤ n, m, k ≤ 100). 

第 2 行,6 个整数 sx, sy, sz, gx, gy, gz(0 ≤ sx, gx ≤ n, 0 ≤ sy, gy ≤ m, 0 ≤ sz, gz ≤ k). 

第 3 行,1 个整数 T(0 ≤ T ≤ 10),表示粉丝团的数量。 

随后 T 行,每行 6 个整数 ai1 , bi1 , ci1 , ai2 , bi2 , ci2

数据保证起点和终点处没有粉丝团,但不同粉丝团之间可能会重叠。

Output

输出一个整数,表示最快时间。如果不能到达 HHU,输出 −1.

Sample Input

6 5 3
0 0 0 6 5 3
2
1 0 0 2 2 3
4 1 0 5 5 3

Sample Output

20

HINT


样例的一条可行路径为:(0,0,0)->(0,1,0)->(0,2,0)->(0,3,0)->(1,3,0)->(2,3,0)->(3,3,0)->(3,2,0)->(3,1,0)-
>(3,0,0)->(4,0,0)->(5,0,0)->(6,0,0)->(6,1,0)->(6,2,0)->(6,3,0)->(6,4,0)->(6,5,0)->(6,5,1)->(6,5,2)-
>(6,5,3) 

Source

[Submit][Status]