March First

Interview

Time limit1sMemory limit1024 MB

Summary

Move water between three sukwoo, where each move cools the water by 5 degrees, to reach the target temperatures and final arrangement in at most 40 moves.

Level: Medium4 of 10
Topics: BFS, Simulation
Solved: No attempts yet

Problem

A tea gathering called 'March First' is held. Members often meet to share tea and dasik (Korean tea confections) and strengthen their friendship.

One day, Choseungdal, the pangju (the person who brews the tea) who leads the gathering, learned the following fact from the owner of a teahouse he often visits.

Each time hot water in a sukwoo is moved to another sukwoo, its temperature drops by $\mathbf{5}$ ℃.

A sukwoo, also called a gongdobae, is a tea utensil used to divide brewed water or to cool the water used for brewing. Having learned that water cools each time it is moved, Choseungdal wants to use the sukwoo he owns to prepare several kinds of water at different target temperatures, so he can brew several kinds of tea at once.

Choseungdal has N sukwoo, numbered 1 to N. Sukwoo 1 to N-1 are filled in order with water 1 to N-1, and sukwoo N is empty. Each of the N-1 waters has a target temperature. The water initially placed in a sukwoo is 100℃. Water can only be moved into an empty sukwoo, and all the water in a sukwoo must be moved.

Move water between sukwoo to lower its temperature until each target is met. Then arrange water 1 to N-1 in the sukwoo so that each water is in its correct sukwoo.

Input

The first line contains the number of sukwoo N. $(N=3)$

The second line contains the target temperatures $t_i$ of water 1 to N-1, separated by spaces. $(5\le t_i\le 100$ , $t_i$ is a multiple of $5$$)$

The third line contains the numbers of the water that must be in sukwoo 1 to N after the moves, separated by spaces. Water numbers are distinct positive integers from 1 to N-1. An empty sukwoo is given as $0$ .

Output

If the goal cannot be reached, print $-1$ on the first line.

Otherwise, print the number of moves $K$ $(0\le K\le 40)$ on the first line. On each of the next $K$ lines, print $x\ y$ , separated by a space, which means the water in sukwoo $x$ is moved to sukwoo $y$ . $x$ and $y$ are distinct positive integers.

If there are several valid methods, print any one of them.

Examples3

Example 1
Input
```
3
95 95
0 1 2
```
Expected output
```
2
2 3
1 2
```
Example 2
Input
```
3
85 90
1 0 2
```
Expected output
```
5
1 3
2 1
3 2
1 3
2 1
```
Example 3
Input
```
3
100 95
2 1 0
```
Expected output
```
-1
```