The Bovine Shuffle
InterviewTime limit2sMemory limit512 MB
Given a permutation describing one shuffle and the cow order after three shuffles, recover the original order before the shuffles.
- Level
Medium4 of 10
- Topics
- Array, Implementation, Simulation, Math
- Solved
- No attempts yet
Problem
Convinced that happy cows give more milk, Farmer John has installed a giant disco ball in his barn and plans to teach his cows to dance.
After looking up popular cow dances, Farmer John settled on the Bovine Shuffle. In the Bovine Shuffle his cows () line up in a row in some order and then perform three shuffles in a row, after which they stand in a possibly different order. To make it easier for the cows to locate themselves, Farmer John numbered the spots in the line through , so the first cow in the lineup stands at position , the next at position , and the last at position .
One shuffle is described by numbers . During the shuffle the cow at position moves to position , and every is between and . Every cow moves to its assigned position during the shuffle. All of the are distinct, so no two cows ever try to move to the same position.
Each of Farmer John's cows carries a 7-digit integer ID, and no two cows share an ID. Given the order of the cows after the three shuffles, determine the order they started in.
Input
The first line contains , the number of cows. The second line contains the integers . The third line contains the order of the cows after three shuffles, with each cow given by its ID.
Output
Print lines giving the order of the cows before the three shuffles, one cow ID per line.