prathams's blog

By prathams, history, 9 years ago, In English

Plane division by a common shape is a very well known topic of computer science. The pictures below shows some such diagrams. In figure 1 we find that four circles divide a plane in maximum 14 zones, four ellipses divide a plane in maximum 26 zones and three triangles divide a plane in maximum 20 zones. It is a common practice to find out the maximum number of regions when m shapes of same type intersects. For example the general formula for circles is m2 - m + 2. When the situation is hybrid (More than one type of shapes intersect) the maximum possible number of regions is also not very difficult to find out.

In figure 2 we can see that eight regions are created when one ellipse and one triangle intersect. In this problem you will have to think in the reverse direction. You will be given the maximum number of regions created and you will have to find how many ellipses, circles and triangles were involved.

Input

The input file contains less than 300 lines of inputs. Each line contains a 32-bit unsigned integer N, which is the maximum number of regions, created by m ellipses, n circles and p triangles. Input is terminated by a line, which contains a –1. This line should not be processed. All input numbers other than the –1 in the last line are positive numbers.

Output

For each line of input you have to produce two or more lines of output. The description of output for each line is given below:

The first line is the serial number of output. Each of the next lines contains three integers. These three integers are possible values of m, n and p for which maximum N regions is created. When there is more than one solution then the solutions should be sorted in ascending of m and then by ascending order of n. If there is no valid solution output a line “Impossible.” instead. Look at the output for sample input for details. Please note that for a valid solution 0 ≤ m < 100, 0 ≤ n < 20000 and 0 ≤ p < 100.

Input Ex

20

10

-1

Output Ex

Case 1:

0 0 3

0 1 2

1 0 2

1 3 0

Case 2:

Impossible.

  • Vote: I like it
  • +12
  • Vote: I do not like it