Blocks

Time limit1sMemory limit128 MB

Summary

Move adjacent block pairs into empty cells in the fewest moves to gather N A's and N B's into separate consecutive groups.

Level: Hard8 of 10
Topics: Simulation, Greedy, Brute force
Solved: No attempts yet

Problem

A $1 \times 4N$ grid has blocks in the rightmost $2N$ cells.

You may pick two consecutive occupied cells and move them to two consecutive empty cells. Block order must be preserved, and the destination must also be two consecutive cells.

Move the blocks the minimum number of times so that $N$ consecutive 'A' blocks and $N$ consecutive 'B' blocks are formed. There are 9 valid final arrangements.

Input

One line with $N$ ( $3 \le N \le 100$ ).

Output

Print moves in the form X to Y, meaning the blocks at cells $X$ and $X+1$ move to cells $Y$ and $Y+1$ ( $-2N+1 \le X, Y \le 2N-1$ , $X \ne Y$ ). Any optimal answer is accepted.

Examples1

Example 1
Input
```
5
```
Expected output
```
8 to -1
3 to 8
6 to 3
0 to 6
9 to 0
```