Baeknam's Journey

Time limit1sMemory limit512 MB

Summary

On an N x N board, output a knight's walk that visits every square at least once using at most 2N^2 total visits, or -1 if impossible.

Level: Medium7 of 10
Topics: Graph, Greedy, Implementation, Simulation
Solved: No attempts yet

Problem

In the world of the chessboard lives Baeknam, a cute white knight. Now that vacation has arrived, Baeknam wants to set off on a journey across the chessboard.

The plan Baeknam has in mind follows these rules.

The chessboard is $N\times N$ in size.
Every square on the chessboard must be visited.
The same square may be visited more than once. However, the total number of square visits must not exceed $2N^2$ .
Baeknam has 8 ways to move, as follows.

Baeknam has an N (Intuitive) MBTI type, so the journey cannot start until every part of the plan is worked out!

Help Baeknam, who is racking his brain over the plan, put together the journey plan!

Input

The first line gives $N$ , the number of rows and also the number of columns of the grid. ( $1\leq N \leq 500$ )

The second line gives integers r and c, the current coordinates of Baeknam. This means the square in row r, column c.

Output

If the journey is judged impossible, output -1.

If the journey is possible, output the total number of square visits $K$ on the first line, then output Baeknam's visited square coordinates in order over the next $K$ lines, one per line.

Examples2

Example 1

Input

5
1 1

Expected output

Example 2
Input
```
3
2 2
```
Expected output
```
-1
```