题目描述

（本题的最初想法非原创，原始链接有剧透，可参见讨论区）

在平面直角坐标系中，你可以每次选择两个格点（$(x,y)$，其中 $x$ 和 $y$ 都是整数的点），然后做出过这两个点的直线。

画出四条这样的直线，可以围成一个正方形，这个正方形具有面积 $S$。

给定面积 $S$，是否存在一种方案能围出这个正方形？如果是，请给出一种构造。

我们只考虑有理数 $S = p / q$ 的情况，而你的输出也必须是精确解。

举例：

• $1/2$、$5/2$、$4/5$ 可以构造
• $1/4$、$2/3$ 不能构造
• $12/15$ 就是 $4/5$，所以可以构造

例如，下面是一个 $4/5$ 的构造

输入格式

第一行是一个整数 $T$，表示总共有 $T$ 组询问

之后 $T$ 行，每行两个整数 $p$、$q$（$0 < p, q < 5 \times 10^6$），表示本次询问的是 $S = p/q$ 的构造。

输出格式

对于每组询问，输出一行：

• 如果给出的面积 $S$ 可以构造，输出 $16$ 个空格分隔的整数表示你的构造，包含：
  • $4$ 条能围成面积为 $S$ 的正方形的线（不必在意线的顺序）
  • 每条线 $2$ 个点
  • 每个点两个整数 $x$ 和 $y$ 表示 $(x, y)$ 这个点，其中，$-2^{64} < x, y < 2^{64}$ （参见“数据范围与提示”）
• 否则，面积 $S$ 不能构造，输出一行 impossible

2
1 3
4 5

impossible
0 0 1 2 1 2 3 1 2 2 1 0 1 1 3 0

数据范围与提示

总共有 $10$ 个测试点，每个测试点记 $10$ 分。其中：

• 测试点 $1$ 的输入如下：

  5
  4999889 3988009
  4012009 4999762
  3674633 4999348
  4997709 2000066
  4782969 1953125
  

• 对于测试点 $2 \dots 5$，$T = 1$
• 对于测试点 $6 \dots 10$，$T = 20000$

虽然检查器使用高精度整数读入答案，但是极不推荐输出绝对值超过 $2^{64}$ 的坐标值 $x$、$y$。这一点不应在解题过程之中产生限制。如果因坐标值绝对值过大且超出此范围，而导致无法正常评测，本题作者不接受为解决此问题改动题目的请求。