Polygon Path Turn Count

Given a regular polygon with n vertices labeled 1, 2, …, n in clockwise order, let the edge e_u be the edge connecting vertex u and vertex (u mod n)+1. A traversal through a triangle is defined as the process of entering the interior of the triangle via one side (called the entry edge) and leaving it via another side (called the exit edge). In such a triangle, if the exit edge is in the clockwise direction with respect to the entry edge, the move is a left turn (denoted by L); otherwise, it is a right turn (denoted by R). For example, in a triangle with vertices A, B, C, if the entry edge is AB then exiting via AC is a left turn (L) and via BC is a right turn (R).

The polygon is partitioned into several triangles (by a valid triangulation). A polygon traversal is defined as starting from one boundary edge of the polygon (the entry edge), crossing through a sequence of triangles and finally leaving the polygon through another boundary edge (the exit edge). It can be shown that for fixed entry and exit edges the path through the polygon is unique, and the entire process can be described by the sequence of turns (each letter being either L or R).

For each pair of distinct edges e_u (entry) and e_v (exit) (with u ≠ v), let:

• \( l_{u,v} \): the number of left turns (L) in the unique path from e_u to e_v.

• \( r_{u,v} \): the number of right turns (R) in the unique path from e_u to e_v.

It turns out that, when the polygon is triangulated in a standard way, the turn sequence is determined solely by the relative positions of u and v. In fact, if we define
\( d = \begin{cases} v-u & \text{if } v > u, \\ v-u+n & \text{if } v < u, \end{cases} \)
then one may show that:

• If \( d \leq \frac{n}{2} \), then the path has only right turns and \( r_{u,v} = d \) (and \( l_{u,v} = 0 \)).

• If \( d > \frac{n}{2} \), then the path has only left turns and \( l_{u,v} = n-d \) (and \( r_{u,v} = 0 \)).

For each \( 1 \le u \le n \), you are to compute the two sums:

• \( S_{L}(u) = \sum_{v \neq u} v \cdot l_{u,v} \)

• \( S_{R}(u) = \sum_{v \neq u} v \cdot r_{u,v} \)

Input: A single integer n representing the number of vertices (and hence edges) of the polygon.

Output: For each u from 1 to n (in order), output a line containing two integers: S_L(u) and S_R(u), separated by a space.

Note: It is guaranteed that the polygon is triangulated in a standard way so that the unique path between any entry edge and exit edge follows the above rules.

inputFormat

The input consists of a single integer n (3 ≤ n ≤ 10⁵, for example) on one line.

outputFormat

Output n lines. For the u-th line (1-indexed), output two integers S_L(u) and S_R(u) separated by a space.

sample

3

3 2
1 3
2 1

</p>