Thinking Backward#1538
Dividing a plane into regions using various shapes is a well-known problem in computer science. The diagrams below illustrate some examples. In Figure 1, four circles divide the plane into at most regions, four ellipses divide the plane into at most regions, and three triangles divide the plane into at most regions. The classic question is to determine the maximum number of regions that can be created by shapes of one type. For circles, for instance, the formula is m^2 - m + 2. When different types of shapes intersect (the hybrid case), finding the maximum possible number of regions is also not difficult.
In Figure 2, we see that eight regions are created by the intersection of one ellipse and one triangle. In this problem, you must solve the reverse task: given the maximum number of regions, find how many ellipses, circles, and triangles could have created it.
The input consists of fewer than lines. Each line contains a -bit unsigned integer —the maximum number of regions created by ellipses, circles, and triangles. The input ends with a line containing , which should not be processed. All numbers except this final are positive.
For each test, output two or more lines. The first line contains its serial number. Each of the following lines contains three integers: possible values of , , and for which regions can be formed. If there is more than one solution, sort them first in increasing , then in increasing . If no solution exists, output the line Impossible. Only print solutions for which 0 \leq m < 100, 0 \leq n < 20000, and 0 \leq p < 100.
Example 1