#4p766j. 三角形 Triangles

时间限制：1 s       空间限制：512 MiB       标签： 数学 构造 计算几何 2022 

算法难度等级：3       思维难度等级：8       实现难度等级：4

平面上有一个正方形。正方形左下角、左上角、右下角和右上角的坐标分别是 $(0,\ 0)$，$(0,\ 10^9)$，$(10^9,\ 0)$ 和 $(10^9,\ 10^9)$。

给定一个正整数 $k$，您需要将该正方形分割成恰好 $k$ 个锐角三角形。也就是说，找到 $k$ 个锐角三角形满足任意两个三角形不相交（但它们可以有一个公共点或一条公共线段）且所有三角形的并等于该正方形。

Input

每个测试文件仅有一组测试数据。

第一行输入一个整数 $k$（$1\leq k\leq 50$）。

Output

如果不存在合法分割，输出 No。

否则首先输出一行 Yes（不输出引号）。接下来 $k$ 行每行输出六个由单个空格分割的数 $x_1,\ y_1,\ x_2,\ y_2,\ x_3$ 和 $y_3$ 表示 $(x_1,\ y_1)$，$(x_2,\ y_2)$ 和 $(x_3,\ y_3)$ 这三个点构成一个锐角三角形。请注意，这 $k$ 个锐角三角形必须是正方形的一个分割。

为了避免精度问题，我们额外限制所有三角形顶点的坐标都必须是整数。可以证明，对于本题所有可能的输入，如果正方形可以被分割成 $k$ 个锐角三角形，则一定存在一个满足所有限制的分割。

Examples

2

No

24

Yes
0 0 500000000 0 400000000 300000000
1000000000 0 500000000 0 600000000 300000000
0 0 0 500000000 300000000 400000000
0 1000000000 0 500000000 300000000 600000000
0 1000000000 500000000 1000000000 400000000 700000000
1000000000 1000000000 500000000 1000000000 600000000 700000000
1000000000 1000000000 1000000000 500000000 700000000 600000000
1000000000 0 1000000000 500000000 700000000 400000000
0 0 400000000 300000000 300000000 400000000
0 500000000 300000000 400000000 300000000 600000000
0 1000000000 300000000 600000000 400000000 700000000
500000000 1000000000 400000000 700000000 600000000 700000000
1000000000 1000000000 600000000 700000000 700000000 600000000
1000000000 500000000 700000000 600000000 700000000 400000000
1000000000 0 700000000 400000000 600000000 300000000
500000000 0 400000000 300000000 600000000 300000000
500000000 500000000 400000000 300000000 300000000 400000000
500000000 500000000 300000000 400000000 300000000 600000000
500000000 500000000 300000000 600000000 400000000 700000000
500000000 500000000 400000000 700000000 600000000 700000000
500000000 500000000 600000000 700000000 700000000 600000000
500000000 500000000 700000000 600000000 700000000 400000000
500000000 500000000 700000000 400000000 600000000 300000000
500000000 500000000 600000000 300000000 400000000 300000000

Note

下图展示了第二组样例数据中的分割方案。