Description

Split the integers $1 \sim 2n$ into $n$ ordered pairs $(a_i, b_i)$ ($1 \le i \le n$). You need to make sure that for every positive integer $i$ not greater than $n$, we have $a_i - b_i = i$.

Given $n$, please provide one construction. If there is no solution, output -1 0.

Input Format

One line with one positive integer $n$.

Output Format

If there is no solution, output one line with two integers -1 0. Otherwise output $n$ lines, each with two positive integers within $1 \sim 2n$, representing $(a_i, b_i)$.

You need to ensure that the $n$ pairs $(a_i, b_i)$, in order of increasing $a_i - b_i$, together form a permutation of the integers $1 \sim 2n$.

2

-1 0

5

2 1
9 7
6 3
8 4
10 5

Hint

Sample Explanation

For the first sample, obviously there is no solution.

For the second sample, the sample output gives a feasible construction.

Constraints and Notes

This problem uses bundled tests.

$\texttt{Subtask 1 (20 pts)}$: $n \le 5$.

$\texttt{Subtask 2 (20 pts)}$: $n \le 10 ^ 5$.

$\texttt{Subtask 3 (30 pts)}$: $n$ is prime.

$\texttt{Subtask 4 (30 pts)}$: no special restrictions.

For $100\%$ of the data, $1 \le n \le 10^6$.

This problem is meant to train mathematical thinking and construction skills, but it is not suitable for OI contests.

CoOI Round 1 Problem B.

Translated by ChatGPT 5