该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

在信息学训练营的几何单元中，导师让同学们练习坐标运算。
给定平面整点 $P_0(x_0,y_0)$ 和一个非负整数 $d$，所有满足

的整点 $P(x,y)$ 构成了一条“菱形”边界，被称为 曼哈顿环。

问题描述

现在有 $T$ 组独立询问。
对于每组询问给出 $(x_0,y_0,d)$，请你输出 按指定顺序 列出所有与 $P_0$ 的曼哈顿距离恰为 $d$ 的整点坐标。

输出顺序要求

• 从最东侧点 $(x_0+d,\;y_0)$ 开始；

• 按逆时针方向依次输出整条环上的点；

• 每个点占一行，先输出横坐标再输出纵坐标，中间用一个空格分隔。

例如 $d=2$ 时，输出顺序应为

$$(x_0+2,y_0)\;\rightarrow\;(x_0+1,y_0+1)\;\rightarrow\;(x_0,y_0+2)\;\rightarrow\;(x_0-1,y_0+1)\;\rightarrow\;(x_0-2,y_0)\;\rightarrow\;\dots $$

输入格式

• 第一行一个整数$T$ — 询问组数，$1 \le T \le 10^2$。

• 对每组询问 输入三个整数$x_0,y_0,d$

  • $|x_0|,|y_0| \le 10^{9}$

  • $0 \le d \le 10^{2}$

输入保证答案坐标均在 $64$ 位有符号整数范围内。

为了避免输出过大，保证所有测试中$\sum_{i=1}^{T} d_i \ \le\ 10^{5}$

输出格式

对每组询问依次输出：

1. 先输出一行一个整数 $k$ ，即本组曼哈顿环上整点的数量；

2. 接着输出 $k$ 行坐标，按照 题目规定的逆时针顺序 列出所有满足条件的点。

任两组询问的输出之间 不要空行。

2
0 0 0
-1 2 2

1
0 0
8
1 2
0 3
-1 4
-2 3
-3 2
-2 1
-1 0
0 1

解释

• 第 1 组：$d=0$，环上只有原点 $(0,0)$。

• 第 2 组：以 $(-1,2)$ 为中心、距离为 $2$的整点共有 $8$ 个，按题目要求逆时针列出。

限制与约束