题目描述

「点」锚定边界，「线」勾勒轮廓，存在就此收束。

擦去一个点，将它两旁的点重新相连，原来的可能性便缺了一角。那一角的面积，便是这个点的「价值」。

你得到了一份记录，上面记着一些点的价值。你想据此推测，它们曾经凝结成怎样的存在。

给定 $n$ 个正整数 $a_1,a_2,\ldots,a_n$。

请在平面直角坐标系中构造 $n+2$ 个互不相同的点 $P_0,P_1,\ldots,P_{n+1}$。每个点的横坐标和纵坐标均须为整数，且满足：

• 按照 $P_0,P_1,\ldots,P_{n+1},P_0$ 的顺序连接各点，得到一个严格凸多边形；
• 对于所有满足 $\boldsymbol{1\le i\le n}$ 的整数 $i$，三角形 $P_{i-1}P_iP_{i+1}$ 的面积恰好为 $a_i$。

严格凸多边形指不自交、且每个内角都严格小于 $180^\circ$ 的多边形。

保证存在满足要求的构造。

输入格式

第一行包含一个整数 $n$（$1\le n\le 2\times10^5$）。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1\le a_i\le 10^7$）。

输出格式

输出 $n+2$ 行。对于 $0\le i\le n+1$，第 $i+1$ 行输出两个整数 $x_i,y_i$，表示顶点 $P_i$ 的坐标。

沿多边形边界依次输出各顶点，顺时针或逆时针均可。

坐标须满足 $|x_i|,|y_i|\le 10^{100}$。

如果有多种合法构造，输出任意一种即可。

1
1

0 0
2 0
0 1

2
3 2

0 0
3 0
5 2
5 4

提示

第一个样例中，三角形 $P_0P_1P_2$ 的底边长为 $2$，对应的高为 $1$，因此面积为 $\frac{2\times 1}{2}=1$。

第二个样例中，三角形 $P_0P_1P_2$ 和 $P_1P_2P_3$ 的面积分别为 $3$ 和 $2$。下图的左右两幅图分别用阴影标出这两个三角形，阴影内的数字表示面积。

样例输出仅展示一种合法构造。