某城市的市长想要在城市周围的十字路口放置 $$$n$$$ 雕像。城市中的交叉点在所有点 $$$(x, y)$$$ 上都有整数坐标。交叉点之间的距离使用曼哈顿距离测量,定义如下: $$\text{distance}((x_1, y_1), (x_2, y_2)) = |x_1 - x_2| + |y_1 - y_2|.$$
市议会对雕像的放置提出了以下要求:
- 第一个雕像放置在$$$(0, 0)$$$;
- 第$$$n$$$个雕像放置在$$$(a, b)$$$;
- 对于 $$$i = 1, \dots, n-1$$$,第 $$$i$$$ 个雕像与第 $$$(i+1)$$$ 个雕像之间的距离为 $$$d_i$$$。
允许在同一个路口放置多个雕像。
帮助市长找到 $$$n$$$ 雕像的有效排列,或者确定它不存在。
输入
第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 50$$$) — 雕像的数量。
第二行包含两个整数 $$$a$$$ 和 $$$b$$$ ($$$0 \le a, b \le 10^9$$$) — 必须放置第 $$$n$$$ 雕像的交叉点坐标。
第三行包含 $$$n-1$$$ 整数 $$$d_1, \dots, d_{n-1}$$$ ($$$0 \le d_i \le 10^9$$$) — 第 $$$i$$$ 个雕像与第 $$$(i+1)$$$ 个雕像之间的距离。
输出
如果 $$$n$$$ 雕像的排列有效,则打印 $$$\texttt{YES}$$$。否则,打印 $$$\texttt{NO}$$$。
如果存在有效排列,请在以下 $$$n$$$ 行中打印有效排列。这些行中的第 $$$i$$$ 必须包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ — 第 $$$i$$$ 雕像放置的交叉点的坐标。如果存在多个有效排列,您可以打印任何有效排列。
示例
输入复制
35 89 0
输出复制
NO
输入复制
410 67 8 5
输出复制
YES 0 0 6 -1 11 2 10 6
注意
在 第一个样本,这 3 个雕像没有有效的排列。
在 第二个样本,示例输出如下图所示。请注意,这并不是 4 座雕像的唯一有效排列。