C. Cut into Squares
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Find a partition of a square into $$$n$$$ squares which may have different sizes, or determine that it is impossible.

Input

The first line of input contains an integer $$$n$$$: the number of squares in the partition ($$$1 \le n \le 50$$$).

Output

If partitioning a square into $$$n$$$ squares is not possible, print "NO" on the first line. Otherwise, print "YES" on the first line, followed by $$$n$$$ lines describing the squares in the partition in any order.

To describe a partition, place the squares so that their sides are parallel to coordinate axes, and vertex coordinates are integers. Each square is denoted by a triple of integers "$$$x$$$ $$$y$$$ $$$s$$$": the coordinates of its bottom left vertex and the side length ($$$0 \le x, y, s \le 10^9$$$, $$$s \gt 0$$$). For example, "4 2 5" denotes a squares with vertices in points $$$(4, 2)$$$, $$$(4, 7)$$$, $$$(9, 2)$$$, and $$$(9, 7)$$$. It can be shown that, if a partition of a square into $$$n \le 50$$$ squares exists at all, there also exists a partition constrained as above.

The list of squares in the output must be a partition of a square: each pair of squares in the list must have no common interior points, and the union of all squares in the list must also be a square.

Examples
Input
2
Output
NO
Input
4
Output
YES
0 0 100000000
100000000 100000000 100000000
100000000 0 100000000
0 100000000 100000000