题目描述

给定两个整数：顶点数 $N$ 和面积 $A$。你需要构造一个具有 $N$ 个顶点的简单多边形，使得其面积恰好为 $\frac{A}{2}$，并且所有顶点均为非负整数坐标，坐标值不超过 $10^9$。

简单多边形满足：

• 定义了一个封闭区域。
• 没有自交，即使在一个点处也不相交。
• 没有两条相邻的边形成平角。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 行。每个测试用例的第一行包含两个整数 $N$ 和 $A$，分别表示多边形的顶点数和所需多边形面积的两倍。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 为 IMPOSSIBLE（如果无法构造满足要求的多边形），否则为 POSSIBLE。

如果输出 POSSIBLE，则再输出 $N$ 行，每行包含两个整数。第 $i$ 行应包含两个整数 $X_i$ 和 $Y_i$，表示第 $i$ 个顶点的坐标。对于每个 $i$，坐标应满足 $0 \le X_i, Y_i \le 10^9$ 的限制。多边形的顶点应按连续顺序列出（在多边形中，$vertex_i$ 应与 $vertex_{i-1}$ 和 $vertex_{i+1}$ 相邻）。

如果存在多个可能的解，你可以输出其中任意一个。

2
4 36
5 2

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

提示

在样例 #1 中，我们可以输出上述坐标为 $(2, 5)$、$(6, 5)$、$(0, 2)$ 和 $(8, 2)$ 的四边形。该四边形的面积为 $18$。

在样例 #2 中，无法构造具有 $5$ 个顶点且面积为 $1$ 的多边形。

:::align{center} :::

限制条件

$1 \le T \le 100$。

$1 \le A \le 10^9$。

测试集 1

$3 \le N \le 5$。

测试集 2

$3 \le N \le 1000$。

翻译由 DeepSeek V4 Pro 完成