Server Relocation

Time limit3sMemory limit1024 MB

Summary

Given N servers in rack A and which ones are manufacturer X, print the fewest moves that send X servers to rack B and Y servers to rack C.

Level: Medium6 of 10
Topics: Recursion, Simulation
Solved: No attempts yet

Problem

A technician is sent to a very narrow server room to move all servers in rack A to racks B and C. Rack A holds servers from two manufacturers. The technician must move all manufacturer X servers to rack B and all manufacturer Y servers to rack C.

Servers can only be inserted into a rack from the top. Each slot has a power supply that works only when the server in that slot consumes less power than the server directly below it. The power supply at the bottom of each rack can power a server from either manufacturer.

The technician may stop only one server at a time. So each move takes the server in the topmost occupied slot of a rack, stops it, places it in the first empty slot of another rack, and restarts it. At no point may a server with higher power consumption be placed on top of one with lower power consumption.

Write a program that finds a plan for moving the servers with the fewest operations.

Input

The first line contains the number of servers in rack A, $N$ ( $1 \le N \le 20$ ), and the number of manufacturer X servers, $K$ ( $0 \le K \le N$ ). The second line contains $K$ server numbers of manufacturer X in increasing order. Servers are numbered $1$ to $N$ in increasing order of power consumption.

Output

Print the operations, one per line. Each line contains the source rack letter, then '->', then the destination rack letter.

Examples1

Example 1
Input
```
3 2
1 3
```
Expected output
```
A->B
A->C
B->C
A->B
C->B
```