配点: $500$ 点

問題文

無限に広がる二次元格子があります。ジャンボ高橋君はこの上でゴルフをすることにしました。

ボールははじめ原点 $(0, 0)$ にあり、ゴールは格子点(座標がいずれも整数である点) $(X, Y)$ です。ジャンボ高橋君は $1$ 打ごとに、次の操作を行えます。

• その時点でボールがある点とのマンハッタン距離が $K$ であるような格子点を $1$ つ選び、その点にボールを飛ばす。

ゴールと同じ座標にボールが来た時点でクリアとなり、それまでの打数がスコアとなります。ジャンボ高橋君はできるだけ少ないスコアでクリアしたいと思っています。

クリアが可能かどうか判定し、可能ならばスコアが最小となるボールの動かし方を $1$ つ求めてください。

制約

• 入力はすべて整数
• $1 \leq K \leq 10^9$
• $-10^5 \leq X, Y \leq 10^5$
• $(X, Y) \neq (0, 0)$

入力

入力は以下の形式で標準入力から与えられます。

$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