Rectilinear Polygon With Area Equal to Its Vertex Count

A rectilinear polygon is a simple polygon whose edges are all parallel to the $x$-axis or the $y$-axis and in which every two consecutive edges are perpendicular (so the edges alternate between horizontal and vertical). The edges never touch or cross, except that two consecutive edges meet at their shared vertex.

You are given an integer $n$. Consider rectilinear polygons that have exactly $n$ vertices and whose area equals exactly $n$. Such a polygon does not exist for every $n$, and when it exists there can be many of them, so this task asks for one specific canonical polygon defined in the Output section.

The input contains a single integer $n$ ($2 \le n \le 10000$), the required number of vertices.

A rectilinear polygon with exactly $n$ vertices and area exactly $n$ exists if and only if $n$ is even and $n \ge 4$. If it does not exist, print a single line containing the word NIE (Polish for "no").

Otherwise print the following canonical polygon. Let $m = n/2 - 1$. Place $m$ unit-width vertical bars standing on the $x$-axis; bar $i$ (for $0 \le i < m$) occupies the strip $i \le x \le i+1$ and has integer height $h_i$, where:

• for $1 \le i < m$: $h_i = 2$ if $i$ is even, and $h_i = 1$ if $i$ is odd;
• $h_0 = n - (h_1 + h_2 + \cdots + h_{m-1})$.

The outline of these bars is a simple rectilinear polygon with exactly $n$ vertices and area exactly $n$. Print its vertices, one per line as two integers x y separated by a space, in counterclockwise order, in exactly this sequence: first $(0, 0)$, then $(m, 0)$, then $(m, h_{m-1})$; then, for $i = m-1, m-2, \ldots, 1$, the two points $(i, h_i)$ and $(i, h_{i-1})$; and finally $(0, h_0)$. (When $m = 1$ the middle sequence is empty, so the polygon is the rectangle $(0,0), (1,0), (1,n), (0,n)$.)

No coordinate exceeds $10^9$ in absolute value.