Thinking Backward

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.

2/2 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 sample output for details. Pleasenotethatforavalidsolution0≤m<100,0≤n<20000and0≤p<100. Sample Input 20 10 -1 Sample Output Case 1: 003 012 102 130 Case 2: Impossible.