K. Square Resistance Value
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Using only resistors with resistance $$$1\;[\Omega]$$$, construct a resistor with resistance $$$\sqrt{D}\;[\Omega]$$$.

You are given a positive integer $$$D$$$. Construct one connected undirected graph satisfying all of the following conditions. Under the constraints of this problem, it can be proven that such a graph always exists.

  • The number of vertices $$$N$$$ is between $$$2$$$ and $$$300$$$, inclusive, and each vertex has a distinct label from $$$1$$$ to $$$N$$$
  • The number of edges $$$M$$$ is at most $$$300$$$, and self-loops and multiple edges are allowed
  • The "effective resistance from vertex $$$1$$$ to vertex $$$N$$$", defined as below, is within an absolute error of $$$\pm 10^{-6}$$$ from $$$\sqrt D$$$

Let $$$G$$$ be a connected undirected graph with $$$n$$$ vertices and $$$m$$$ edges $$$(n\geq2)$$$, and suppose that the $$$j$$$-th edge connects vertices $$$a_j,b_j$$$. Consider assigning a real number $$$V_i\;(i=1,2,\cdots,n)$$$ to each vertex of graph $$$G$$$, and a real number $$$I_j\;(j=1,2,\cdots,m)$$$ to each edge, so that all of the following equations are satisfied.

  • $$$I_j = V_{a_j}-V_{b_j}\;\;(j=1,2,\cdots,m)$$$
  • $$$\displaystyle\sum_{b_j=i} I_j-\sum_{a_j=i}I_j = 0\;\;(i=2,3,\cdots,n-1)$$$
  • $$$\displaystyle\sum_{b_j=n} I_j-\sum_{a_j=n}I_j = 1$$$

It can be proven that such an assignment always exists, and furthermore that the value of $$$V_1-V_n$$$ is uniquely determined. We define this value as the "effective resistance from vertex $$$1$$$ to vertex $$$n$$$".

Input

The input consists of a single positive integer $$$D$$$. ($$$1 \leq D \leq 5000$$$)

Output

On the first line, print the number of vertices $$$N$$$ and the number of edges $$$M$$$ of the constructed graph, in this order, separated by spaces.

On each of the following $$$M$$$ lines, the $$$i$$$-th line $$$(i=1,2,\cdots, M)$$$ should contain the endpoints of the $$$i$$$-th chosen edge, separated by a space.

If there are multiple graphs satisfying the conditions, any one of them may be printed.

Example
Input
1
Output
4 5
1 2
1 3
2 3
2 4
3 4
Note

The following is an illustration of the output for the first example.

That the effective resistance from vertex $$$1$$$ to vertex $$$n$$$ is $$$1\;[\Omega]$$$ can be explained as follows.

  • Since all resistors have resistance $$$1\;[\Omega]$$$, and by symmetry the potentials at vertices $$$2$$$ and $$$3$$$ are equal, the resistor between them can be treated as if it does not exist.
  • As a result, the circuit reduces to two branches in parallel, each branch consisting of two $$$1\;[\Omega]$$$ resistors in series.
  • The effective resistance of two $$$1\;[\Omega]$$$ resistors in series is $$$2\;[\Omega]$$$, and the effective resistance of two $$$2\;[\Omega]$$$ resistors in parallel is $$$1\;[\Omega]$$$.

The following output is also considered correct.

2 1
1 2