Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3371
Cheater's Shuffle

Time Limit: 30 Seconds      Memory Limit: 81920 KB      Special Judge

Many card cheaters tricks are based on the shuffling of the deck. Collecting the cards from the table and shuffling the deck in a special way, the cheater may get the desired order of the cards. In this problem you have to model the process to see that the cheater can often reach his goal.

The deck contains n cards. The shuffling consists of exactly t moves. There are p ways to make each move. The i-th way to make some move is the following. The shuffler picks mi + li cards from the top of the deck and moves them to the bottom of the deck. There he drops the last li cards picked, letting them stay at the bottom of the deck, and returns the other mi cards to the top of the deck. The order of the cards within the blocks of li and mi cards, and the cards staying in the deck remains the same.

Given the initial order of the cards in the deck, the desired order, and the parameters of the shuffle, find out whether it is possible to reorder the cards in the specified way.


The first line of the input file contains n, t, and p (2 ≤ n ≤ 36, 1 ≤ t ≤ 15, 1 ≤ p ≤ 5). The next two lines contain the initial and the desired order of the cards respectively. Cards are identified by integer numbers from 1 to n, all cards are different, the cards are listed from the bottom of the deck to its top.

The following p lines contain two numbers each --- mi and li (1 ≤ li < n, 0 ≤ mi < n, li + mi < n).

There are multiple cases. Process to the end of file.


If it is impossible to reoreder the cards in the required way using exactly t shuffling moves, output "Impossible"" on the first line of the output file. In the other case output t integer numbers --- in which way to perform each move.

Sample Input

6 3 2
1 2 3 4 5 6
4 5 1 2 3 6
1 2
1 3
6 2 2
1 2 3 4 5 6
4 5 1 2 3 6
1 2
1 3

Sample Output

1 1 2

Author: Andrew Stankevich
Source: Andrew Stankevich's Contest #11
Submit    Status