Restore the Original (small)

Interview

Time limit1sMemory limit1024 MB

Summary

Given the deck after K shuffles and the shuffle order D, recover the original arrangement by applying the inverse shuffle K times.

Level: Medium5 of 10
Topics: Array, Simulation, Implementation, Math
Solved: No attempts yet

Problem

There are $N$ cards, each with one of the numbers $P_1, P_2, \cdots, P_N$ written on it.

There is a sequence $D_1, D_2, \cdots, D_i, \cdots, D_N$ that contains each number from 1 to $N$ exactly once. For each $i$ , the operation of taking the $D_i$ -th card to position $i$ is called a shuffle.

For example, suppose $P_1, P_2, \cdots, P_N$ is 1, 4, 5, 3, 2 and $D_1, D_2, \cdots, D_N$ is 4, 3, 1, 2, 5. Shuffling this deck once gives 3, 5, 1, 4, 2. In the figure below, $S$ is the deck after one shuffle.

You know the deck after $K$ shuffles by this method, and you know $D$ . Find the original arrangement of the cards.

Input

The first line gives the number of cards $N$ and the number of shuffles $K$ , separated by a space.

The second line gives $N$ values $S_i$ , separated by spaces, describing the deck after $K$ shuffles.

The third line gives $N$ values $D_i$ , separated by spaces.

Output

Print the original arrangement, the values $P_1$ through $P_N$ , separated by spaces.

Constraints

$1 \le N \le 10^4$
$1 \le K \le 10^3$
$1 \le D_i \le N$
$1 \le P_i, S_i \le 10^6$
$P_i$ is an integer

Examples2

Example 1
Input
```
5 2
4 1 3 5 2
4 3 1 2 5
```
Expected output
```
1 4 5 3 2
```
Example 2
Input
```
4 1
4 3 2 1
4 3 2 1
```
Expected output
```
1 2 3 4
```