#216849. [GKS 2021 #G] Simple Polygon

You are given integers, the number of vertices and area . You need to construct a simple polygon of vertices such that the area of the polygon is exactly , and all the vertices have non-negative integer coordinates with value up to .

A simple polygon is one that:

• Defines a closed area.
• Does not have self-intersections, even at a single point.
• No consecutive edges form a straight angle.

The st line of the input gives the number of test cases, . lines follow. The st line of each test case contains integers, denoting the number of vertices and , denoting double the required area of the polygon.

For each test case, output line containing Case # : , where is the test case number (starting from ) and is IMPOSSIBLE if it is not possible to construct a polygon with the given requirements and POSSIBLE otherwise.

If you output POSSIBLE, output more lines with integers each. The -th line should contain integers and which denote the coordinates of the -th vertex. For each , the coordinates should satisfy the constraints. Vertices of the polygon should be listed in consecutive order ( should be adjacent to and in the polygon).

If there are multiple possible solutions, you can output any of them.

样例输入 1

2
4 36
5 2

样例输出 1

Case #1: POSSIBLE
2 5
6 5
8 2
0 2
Case #2: IMPOSSIBLE

In Sample Case #, we can output the above quadrilateral with coordinates , , and . The area of this quadrilateral is equal to .

In Sample Case #, there is no way to construct a polygon with vertices and area equal to .

:::align{center} :::

Limits

.

.

Test Set

.

Test Set

.