Dividing SpaceLand into 27 Regions

In this problem, you are given the number of cities in SpaceLand, their coordinates in 3D space, and an array of 27 integers. These 27 integers represent the expected number of cities in each region after dividing SpaceLand into 27 parts using 6 planes (2 for each coordinate axis).

The goal is to determine the positions of three pairs of parallel planes (one pair for each axis) such that when the cities are partitioned into regions by these planes, the number of cities in each region matches exactly the given list. If such a division is possible, output the positions of each pair of planes; otherwise, output -1.

For each axis, let the unique sorted coordinates be (x_1, x_2, x_3, \dots). The candidate planes are given by the formulas: [ x_{plane1} = x_1 + \frac{x_2 - x_1}{2}, \quad x_{plane2} = x_2 + \frac{x_3 - x_2}{2} ] and similarly for the y-axis and z-axis.

Each city is assigned to a region based on its coordinate relative to the plane positions. The program should read the input from standard input and output the result to standard output.

inputFormat

The input is read from standard input in the following format:

The first line contains a single integer (n) representing the number of cities.

The next (n) lines each contain three space-separated integers representing the coordinates (x), (y), and (z) of a city.

The final line contains 27 space-separated integers representing the expected number of cities in each of the 27 regions.

outputFormat

Output to standard output. If a valid division exists, print three lines:

• The first line contains two floating-point numbers representing the positions of the two planes on the x-axis.
• The second line contains two floating-point numbers for the y-axis.
• The third line contains two floating-point numbers for the z-axis.

If no valid division is found, print -1.## sample

27
1 1 1
1 1 2
1 1 3
1 2 1
1 2 2
1 2 3
1 3 1
1 3 2
1 3 3
2 1 1
2 1 2
2 1 3
2 2 1
2 2 2
2 2 3
2 3 1
2 3 2
2 3 3
3 1 1
3 1 2
3 1 3
3 2 1
3 2 2
3 2 3
3 3 1
3 3 2
3 3 3
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

-1