#ABC135E. Golf

Golf

题目描述

Jumbo Takahashi will play golf on an infinite two-dimensional grid.

The ball is initially at the origin (0,0)(0, 0), and the goal is a grid point (a point with integer coordinates) (X,Y)(X, Y). In one stroke, Jumbo Takahashi can perform the following operation:

  • Choose a grid point whose Manhattan distance from the current position of the ball is KK, and send the ball to that point.

The game is finished when the ball reaches the goal, and the score will be the number of strokes so far. Jumbo Takahashi wants to finish the game with the lowest score possible.

Determine if the game can be finished. If the answer is yes, find one way to bring the ball to the goal with the lowest score possible.

What is Manhattan distance?

The Manhattan distance between two points (x1,y1)(x_1, y_1) and (x2,y2)(x_2, y_2) is defined as x1x2+y1y2|x_1-x_2|+|y_1-y_2|.

高桥珍宝将在一个无限大的二维网格上打高尔夫球。

球最初位于原点 (0,0)(0, 0) ,目标是网格点(坐标为整数的点) (X,Y)(X, Y) 。在一次击球中,高桥珍宝可以执行以下操作:

  • 选择一个与小球当前位置的曼哈顿距离为 KK 的网格点,并将小球送到该点。

当球到达球门时,游戏结束,得分就是到目前为止的击球次数。高桥珍宝希望以尽可能低的分数结束比赛。

请判断比赛能否结束。如果答案是肯定的,请找出一种方法,使球以尽可能低的分数到达球门。

曼哈顿距离是多少?

两点 (x1,y1)(x_1, y_1)(x2,y2)(x_2, y_2) 之间的曼哈顿距离定义为 x1x2+y1y2|x_1-x_2|+|y_1-y_2|

输入格式

输入内容按以下格式标准输入:

KK
XX YY

输出格式

如果游戏无法结束,则打印 -1

如果游戏可以结束,则按以下格式打印一种将球带到终点且得分最低的方法:

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

这里, ss 是可能的最低得分, (xi,yi)(x_i, y_i) 是球在第 ii 次击球后的位置。

样例 #1

样例输入 #1

11
-1 2

样例输出 #1

3
7 4
2 10
-1 2

样例 #2

样例输入 #2

4600
52 149

样例输出 #2

-1

样例 #3

样例输入 #3

4
9 9

样例输出 #3

5
1 3
4 2
4 6
6 8
9 9

说明

数据规模与约定

  • 输入值均为整数
  • 1K1091 \leq K \leq 10^9
  • 105X,Y105-10^5 \leq X, Y \leq 10^5
  • (X,Y)(0,0)(X, Y) \neq (0, 0)

样例 11 解释

  • (0,0)(0, 0)(7,4)(7, 4) 之间的曼哈顿距离是 07+04=11|0-7|+|0-4|=11
  • (7,4)(7, 4)(2,10)(2, 10) 之间的曼哈顿距离是 72+410=11|7-2|+|4-10|=11
  • (2,10)(2, 10)(1,2)(-1, 2) 之间的曼哈顿距离为 2(1)+102=11|2-(-1)|+|10-2|=11

因此,这个下法是有效的。

此外,也不可能以少于三划的优势结束对局。