Problem Description

Translated from COCI 2019/2020 Contest #6 T3. Konstrukcija

Let $G$ be a directed acyclic graph. If distinct vertices $c_1, c_2, c_3, \ldots, c_n$ in $G$ satisfy the condition that there is a path from $c_1$ to $c_2$, a path from $c_2$ to $c_3$, and so on, up to a path from $c_{n-1}$ to $c_n$, then the array $C = (c_1, c_2, c_3, \ldots, c_n)$ is called an ordered array starting at $c_1$ and ending at $c_n$.

Note that for any two adjacent elements $c_i, c_{i+1}$ in $C$, there does not necessarily need to be a direct edge between them, just a path.

We also define the length of the ordered array $C = (c_1, c_2, c_3, \ldots, c_n)$ as $\mathrm{len}(C) = n$. Thus, the length of an ordered array is the number of vertices it contains. Note that there can be an ordered array of length 1, starting and ending at the same point.

Furthermore, we define the sign of the ordered array $C = (c_1, c_2, c_3, \ldots, c_n)$ as $\mathrm{sgn}(C) = (-1)^{\mathrm{len}(C)+1}$.

For vertices $x, y$ in $G$, we denote by $S_{x,y}$ the set of all ordered arrays starting at $x$ and ending at $y$.

Finally, we define the contradiction value between vertices $x$ and $y$ as $\mathrm{tns}(x,y) = \sum\limits_{C \in S_{x,y}} \mathrm{sgn}(C)$. That is, the contradiction value between vertices $x$ and $y$ is the sum of the signs of all ordered arrays starting at $x$ and ending at $y$.

Given an integer $K$, you need to construct a directed acyclic graph with at most 1000 vertices and 1000 edges such that $\mathrm{tns}(1,N) = K$, where $N$ is the number of vertices. The vertices are numbered from 1 to $N$.

Input Format

The first line contains an integer $K$.

Output Format

The first line contains two integers $N$ and $M$, representing the number of vertices and edges in the constructed directed acyclic graph, respectively.

The following $M$ lines each contain two distinct integers $X_i$ and $Y_i$, indicating that the $i$-th edge goes from $X_i$ to $Y_i$. Each edge should appear at most once.

Your solution must ensure that the absolute value of the contradiction value between any two points does not exceed $2^{80}$. If there are multiple solutions, any one will suffice.

Sample Input and Output

Sample Input #1

0

Sample Output #1

6 6
1 4
1 5
4 3
5 3
3 2
2 6

Sample Input #2

1

Sample Output #2

1 0

Sample Input #3

2

Sample Output #3

6 8
1 2
1 3
1 4
1 5
5 4
2 6
3 6
4 6

Notes

Sample 1 Explanation

The constructed graph contains 6 vertices. The ordered arrays starting at 1 and ending at 6 are:

• $(1, 6)$;
• $(1, 4, 6)$;
• $(1, 5, 6)$;
• $(1, 3, 6)$;
• $(1, 2, 6)$;
• $(1, 4, 3, 6)$;
• $(1, 4, 2, 6)$;
• $(1, 5, 3, 6)$;
• $(1, 5, 2, 6)$;
• $(1, 3, 2, 6)$;
• $(1, 4, 3, 2, 6)$;
• $(1, 5, 3, 2, 6)$.

Their lengths are $1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4$, respectively,
so their signs are $-1, 1, 1, 1, 1, -1, -1, -1, -1, -1, 1, 1$.
Therefore, the contradiction value between 1 and 6 is $-1 + 1 + 1 + 1 + 1 - 1 - 1 - 1 - 1 - 1 + 1 + 1 = 0$.

Data Range

For $100\%$ of the data, $|K| \le 10^{18}$.

Subtask constraints are as follows:

见题面 Input 部分

见题面 Output 部分