Let ~G~ be a directed acyclic graph. If ~c_1, c_2, \dots, c_n~ are distinct vertices of ~G~ such that there is a path from ~c_1~ to ~c_2~, there is a path from ~c_2~ to ~c_3~, …, and there is a path from ~c_{n-1}~ to ~c_n~, we say that array ~C = (c_1, c_2, \dots, c_n)~ is an ordered array starting at ~c_1~ and ending at ~c_n~. Note that between neighbouring elements ~c_i~ and ~c_{i+1}~ of ordered array ~C~ it isn't necessary to exist a direct edge, it is enough for the path to exist from ~c_i~ to ~c_{i+1}~.

For this definition of an ordered array ~C = (c_1, c_2, \dots, c_n)~, we define its length ~len(C) = n~. Therefore, the length of an ordered array is equal to the number of vertices it holds. Note that the ordered array can have a length of ~1~ when holding a single vertex which represents both its beginning and its end.

Also, for an ordered array ~C = (c_1, c_2, \dots, c_n)~ we can define its sign as ~sgn(C) = (-1)^{len(C)+1}~. For vertices ~x~ and ~y~ of ~G~, let's denote with ~S_{x,y}~ a set of all ordered arrays that start in ~x~ and end in ~y~.

Finally, we define the tension between nodes ~x~ and ~y~ as ~tns(x, y) = \sum_{C \in S_{x,y}} sgn(C)~. Therefore, the tension between nodes ~x~ and ~y~ equals the sum of signs of all ordered arrays that start in ~x~ and end in ~y~.

An integer ~K~ is given. Your task is to construct a directed acyclic graph with at most ~1\,000~ vertices and at most ~1\,000~ edges for which ~tns(1, N) = K~ holds. Number ~N~ in the previous expression denotes the number of vertices in a graph. Vertices of a graph should be indexed using positive integers from ~1~ to ~N~.

Input Specification

The first line contains an integer ~K~ ~(|K| \le 10^{18})~ from the task description.

Output Specification

In the first line you should output the number of vertices and the number of edges of the constructed graph. Let's denote the number of vertices of that graph with ~N~ ~(1 \le N \le 1\,000)~, and the number of edges with ~M~ ~(0 \le M \le 1\,000)~.

In the ~i~-th of the next ~M~ lines you should output two distinct integers ~X_i~ and ~Y_i~ ~(1 \le X_i, Y_i \le N)~, which represent the ~i~-th edge which is directed from vertex with index ~X_i~ towards vertex with index ~Y_i~. Each edge must appear only once in the output.

Also, the absolute value of tension between each two nodes in the graph must be less or equal to ~2^{80}~. If there are multiple solutions, output any of them.

Constraints

Subtask	Points	Constraints
1	15	~1 \le K < 500~
2	15	~-300 < K \le -1~
3	20	~|K| < 10\,000~
4	60	No additional constraints.

Sample Input 1

0

Sample Output 1

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

Explanation of Sample Output 1

The constructed graph has ~6~ vertices. Ordered arrays that start in ~1~ and end in ~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 (in order): ~1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4~, so their signs are ~-1, 1, 1, 1, 1, -1, -1, -1, -1, -1, 1, 1~. Therefore, the tension between ~1~ and ~6~ is equal to ~-1 + 1 + 1 + 1 + 1 - 1 - 1 - 1 - 1 - 1 + 1 + 1 = 0~.

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