设 $G$ 是一个有向无环图。如果 $c_1, c_2, c_3, \dots, c_n$ 是 $G$ 的互不相同的顶点，且满足从 $c_1$ 到 $c_2$ 存在路径，从 $c_2$ 到 $c_3$ 存在路径，……，以及从 $c_{n-1}$ 到 $c_n$ 存在路径，我们称序列 $C = (c_1, c_2, c_3, \dots, c_n)$ 是一个起点为 $c_1$、终点为 $c_n$ 的有序序列。注意，在有序序列 $C$ 中，相邻的两个元素 $c_i$ 和 $c_{i+1}$ 之间不一定需要存在直接的有向边，只需存在从 $c_i$ 到 $c_{i+1}$ 的路径即可。

对于上述定义的有序序列 $C = (c_1, c_2, c_3, \dots, c_n)$，我们定义其长度为 $\text{len}(C) = n$。因此，一个有序序列的长度等于它所包含的顶点个数。注意，当有序序列仅包含一个顶点时，其长度可以为 1，此时该顶点既是起点也是终点。

此外，对于有序序列 $C = (c_1, c_2, c_3, \dots, c_n)$，我们定义其符号为 $\text{sgn}(C) = (-1)^{\text{len}(C)+1}$。对于 $G$ 中的顶点 $x$ 和 $y$，我们用 $S_{x,y}$ 表示所有起点为 $x$ 且终点为 $y$ 的有序序列的集合。

最后，我们定义节点 $x$ 和 $y$ 之间的张力（tension）为：

$$\text{tns}(x, y) = \sum_{C \in S_{x,y}} \text{sgn}(C)$$

因此，节点 $x$ 和 $y$ 之间的张力等于所有起点为 $x$ 且终点为 $y$ 的有序序列的符号之和。

给定一个整数 $K$。你的任务是构造一个最多包含 $1000$ 个顶点和最多 $1000$ 条边的有向无环图，使得 $\text{tns}(1, N) = K$ 成立。其中 $N$ 表示图中的顶点数。图中的顶点应使用从 $1$ 到 $N$ 的正整数进行编号。

输入格式

第一行包含一个整数 $K$（$|K| \le 10^{18}$），含义如题面所述。

输出格式

第一行输出构造的图的顶点数和边数。用 $N$（$1 \le N \le 1000$）表示该图的顶点数，用 $M$（$0 \le M \le 1000$）表示边数。

接下来的 $M$ 行中，每行输出两个不同的整数 $X_i$ 和 $Y_i$（$1 \le X_i, Y_i \le N$），表示一条从顶点 $X_i$ 指向顶点 $Y_i$ 的有向边。每条边在输出中只能出现一次。

此外，图中任意两个节点之间的张力的绝对值必须小于或等于 $2^{80}$。

如果存在多个解，输出其中任意一个即可。

数据范围

样例

输入样例 1

0

输出样例 1

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

输入样例 2

1

输出样例 2

1 0

输入样例 3

2

输出样例 3

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

说明

样例 1 说明：

构造的图有 6 个顶点。起点为 1 且终点为 6 的有序序列有：$(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)$。

它们的长度依次为：1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4，因此它们的符号依次为：$-1, 1, 1, 1, 1, -1, -1, -1, -1, -1, 1, 1$。

因此，1 和 6 之间的张力等于 $-1 + 1 + 1 + 1 + 1 - 1 - 1 - 1 - 1 - 1 + 1 + 1 = 0$。