Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2515
Height of Water Tower

Time Limit: 2 Seconds      Memory Limit: 65536 KB

ACM Corporation decides to build a water tower for a neighborhood which can reduce the number of complaints from residents about the water supply system. However, the corporation does not plan to build the tower too high, otherwise there will be complaints about the sight view from those captious residents. So the corporation needs to calculate the least height of this water tower.

The pipe network in this area is really tough. Everybody will be confused by looking at the graph of the network. It seems impossible to complete this task without the help of computer. Now it is your turn.

Input

The input consists of multiple test cases. Each test case divides into two sections. The first section starts with a positive integer N (<=1000) which represents the number of pipe segments in the area. The following N lines give out the description of pipe segments. Each line consists of 6 positive integers: x1, y1, z1, x2, y2, z2, which are the coordinate of its two endpoints. If two pipes share the same endpoint, they are considered as connected. All pipe segments are connected to the same network. The second section starts with a non-negative integer M which represents the number of hydrants installed in the neighborhood. The next M lines give out the description of all hydrants. Each line consists of 3 positive integers: x, y, z, which is the coordinate of the hydrant. All hydrants are installed on the endpoints of a pipe segment.

There is always a pipe that has an endpoint on (0, 0, 0), which is the connection point between the tower and the network.

Output

For each test case, output the minimum height of the water tower in a single line.

Sample Input:
3
0 0 0 0 0 1
0 0 1 0 1 1
0 0 0 0 3 2
1
0 3 2
Sample Output:
2


Author: XU, Chuan
Source: CYJJ's Funny Contest #1, Killing in Seconds
Submit    Status