
ZOJ Problem Set  3371
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 ith way to make some move is the following. The shuffler picks m_{i} + l_{i} cards from the top of the deck and moves them to the bottom of the deck. There he drops the last l_{i} cards picked, letting them stay at the bottom of the deck, and returns the other m_{i} cards to the top of the deck. The order of the cards within the blocks of l_{i} and m_{i} 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. InputThe 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  m_{i} and l_{i} (1 ≤ l_{i} < n, 0 ≤ m_{i} < n, l_{i} + m_{i} < n). There are multiple cases. Process to the end of file. OutputIf 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 Input6 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 Output1 1 2 Impossible Author: Andrew Stankevich Source: Andrew Stankevich's Contest #11 