Graph Construction for Contradiction Value

Given an integer (K), construct a directed acyclic graph (DAG) with at most 1000 vertices and 1000 edges such that the contradiction value between vertex 1 and vertex (N) equals (K), where (N) is the total number of vertices.

Definitions:

1. Let (G) be a DAG. An ordered array (C = (c_1, c_2, \ldots, c_n)) (with (n \ge 1)) is called an ordered array from (c_1) to (c_n) if for every adjacent pair (c_i, c_{i+1}) there exists a path (not necessarily a direct edge) from (c_i) to (c_{i+1}).
   
2. Define (\mathrm{len}(C) = n) and the sign (\mathrm{sgn}(C) = (-1)^{n+1}).
   
3. For vertices (x,y), let (S_{x,y}) be the set of all ordered arrays from (x) to (y).
   
4. The contradiction value is defined as (\mathrm{tns}(x,y) = \sum_{C \in S_{x,y}} \mathrm{sgn}(C)).
   
   Your task is to construct a DAG with vertices numbered (1) to (N) ((N) is determined by your construction) such that (\mathrm{tns}(1,N)=K).
   
   Output Format: First output two integers (N) and (M) (the number of vertices and edges respectively), followed by (M) lines each containing two integers (u) and (v) denoting a directed edge from (u) to (v>.

inputFormat

The input consists of a single integer (K).

outputFormat

Output a valid DAG that satisfies (\mathrm{tns}(1,N)=K). The first line should contain two integers (N) and (M), the number of vertices and edges respectively. Each of the following (M) lines should contain two integers (u) and (v), representing a directed edge from vertex (u) to vertex (v).

sample

1

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