## HANOI - Nightmare in the Towers of Hanoi

Consider the folowing variation of the well know problem Towers of Hanoi:

We are given *n* towers and *m* disks of sizes 1,2,3,...,*m* stacked on some towers. Your objective is to transfer all the disks to the *k*-th tower in as few moves as you can manage, but taking into account the following rules:

- moving only one disk at a time,
- never moving a larger disk one onto a smaller one,
- moving only between towers at distance at most
*d*.

You can assume that all the problems can be solved in not more than 20000 moves.

### Input

The first line of input contains a single positive integer *t* <= 1000, the number of test cases.

Each tests case begins with the number of towers 3 <= *n* <= 100, the number of target tower 1 <= *k* <= *n*, the number of disks *m* <= 100 and the maximum distance 1 <= *d* <= *n* - 1.

Then, the following *m* lines consists of pairs of numbers describing the initial situation, in the form: the tower and disk on it. Assume according to the rules that on every tower smaller disks are on larger disks.

### Output

Process all test cases. The correct output for the *i*-th test case takes the following form:
*i* [the number of the test case (in input order)]
*a b* [a sequence of lines of this form, where *a* is the tower with the moved disk on top of it and *b* is the target tower].

The test case is considered solved if after performing the sequence all disks are on the *k*-th tower. At the end of the series of moves you should always write a line consisting of two zeros ('0 0').

### Scoring

The score awarded to your program is the sum of scores for individual test cases. For the i-th test case you will receive *T _{i}* / (

*T*+

_{i}*A*) points, where

_{i}*T*<= 20000 and

_{i}*A*is the number of moves in your solution. If you don't want to solve a test case, you may output the line '0 0' without a list of moves, for which you will not be awarded any points. Your program may not write more than 30000 kB to output (this will result in SIGXFSZ).

_{i}### Example

Input5 3 3 3 2 1 1 1 2 1 3 3 1 3 2 1 1 1 2 1 3 4 4 4 2 1 1 1 2 1 3 1 4 4 4 4 2 1 1 1 2 2 4 4 3 4 4 4 3 1 1 4 2 4 3 4 4Output1 1 3 1 2 3 2 1 3 2 1 2 3 1 3 0 0 2 0 0 3 0 0 4 4 3 2 4 3 4 1 2 1 3 3 4 2 4 0 0 5 1 2 0 0ScoreAssuming:T= {7,6,15,7,1} the output will receive2points.

*Bonus info:* If score = *xxx*.*xxxaaa*, *aaa* means the number of test cases with non-zero score...

Added by: | mima |

Date: | 2004-10-27 |

Time limit: | 17s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: NODEJS PERL6 VB.NET |

Resource: | - |