高尔夫

题目描述

有一个无限延伸的二维网格。Jumbo Takahashi 君决定在上面打高尔夫。

球一开始在原点 $(0, 0)$,目标是格点(两个坐标都是整数的点)$(X, Y)$。Jumbo Takahashi 君每打 1 杆,可以执行以下操作:

• 选择一个与球当前所在点的曼哈顿距离为 $K$ 的格点,把球打到那个点。

当球到达与目标相同的坐标时即通关,到此为止的杆数就是得分。Jumbo Takahashi 君希望用尽可能少的得分通关。

请判断能否通关,如果可能,请找出一种使得分最小的球的移动方式。

关于曼哈顿距离:

两个坐标 $(x_1, y_1), (x_2, y_2)$ 之间的曼哈顿距离定义为 $|x_1-x_2|+|y_1-y_2|$。

输入格式

输入按以下格式从标准输入给出:

$K$
$X$ $Y$

输出格式

如果无法通关,输出 -1。

如果能够通关,请按以下格式输出一种得分最小的球的移动方式:

$s$
$x_1$ $y_1$
$x_2$ $y_2$
$.$
$.$
$.$
$x_s$ $y_s$

这里,$s$ 是最小得分,$(x_i, y_i)$ 是第 $i$ 杆把球打到的目标的坐标。

样例

11
-1 2

3
7 4
2 10
-1 2

$(0, 0)$ 与 $(7, 4)$ 的曼哈顿距离为 $|0-7|+|0-4|=11$。

$(7, 4)$ 与 $(2, 10)$ 的曼哈顿距离为 $|7-2|+|4-10|=11$。

$(2, 10)$ 与 $(-1, 2)$ 的曼哈顿距离为 $|2-(-1)|+|10-2|=11$。

综上,这种球的移动方式是合法的。

另外,不存在少于 3 杆就通关的方法。

4600
52 149

-1

4
9 9

5
1 3
4 2
4 6
6 8
9 9

数据范围

• 输入均为整数
• $1 \le K \le 10^9$
• $-10^5 \le X, Y \le 10^5$
• $(X, Y) \neq (0, 0)$

提示

答案不唯一,输出任意合法解即可。