Beautiful Road Network

Vera loves hiking, so she wants to build her own road network. The network consists of \(v\) locations numbered \(1,2,\dots,v\) and \(e\) bidirectional roads. Each road connects two locations \(a_i\) and \(b_i\). The network is guaranteed to be connected and may contain multiple roads between the same two locations.

Vera calls a pair of distinct locations \((a,b)\) with \(a < b\) a perfect pair if there exists a cycle starting at \(a\), going to \(b\), and then returning to \(a\) such that each road is used at most once. In other words, a pair \((a,b)\) is perfect if there exists a simple cycle that contains both \(a\) and \(b\). She considers her road network beautiful if it contains exactly \(k\) perfect pairs.

Your task is: Given an integer \(k\), construct a beautiful road network. It can be shown that if a beautiful network exists then one can always construct one where the set of vertices that lie on some cycle forms a simple cycle. In a simple cycle of \(n\) vertices, every pair of distinct vertices forms a perfect pair, and hence the number of perfect pairs is \[ {n \times (n-1) \over 2}. \] Therefore, if we can find an integer \(n\) (with \(n \ge 2\)) such that \[ {n(n-1) \over 2} = k, \] then a solution is to construct a cycle on \(n\) vertices. Note that when \(n=2\) a simple cycle cannot be formed with a single edge, but since multiple roads are allowed, you can use two parallel roads connecting vertices 1 and 2 to form a cycle.

If no such integer exists, output -1 (for this problem, you may assume that the input \(k\) will always be such that a solution exists).

inputFormat

The input consists of a single integer \(k\) (\(1 \le k \le 10^9\)). It is guaranteed that there exists an integer \(n\) (with \(n \ge 2\)) such that \(n(n-1)/2=k\).

outputFormat

If \(n\) is the unique integer for which \(n(n-1)/2=k\), then output the description of the constructed road network in the following format:

v e
a1 b1
a2 b2
... 
 a_e b_e

where \(v=n\) is the number of locations and \(e\) is the number of roads. For \(n \ge 3\), you can output a simple cycle with edges \((1,2), (2,3), \dots, (n-1,n), (n,1)\). For \(n=2\), output two roads connecting 1 and 2 (i.e. two parallel edges) so that there is a cycle involving vertices 1 and 2.

sample

1

2 2
1 2
1 2