Where the Dancers Stand After K Beats

Dancers stand in a line of n positions; line[i] is the name of the dancer at position i. The routine is fixed: on every beat, the dancer standing at position i moves to position moves[i]. Every position is the destination of exactly one move, so moves is an arrangement of the numbers 0 to n - 1, and all dancers move at the same moment.

Return the line (a new list of names, by position) after exactly k beats.

Examples

Input:  line = ["A", "B", "C", "D"], moves = [1, 2, 0, 3], k = 1
Output: ["C", "A", "B", "D"]
Explanation: A goes to 1, B to 2, C to 0, and D stays at 3.

Input:  line = ["A", "B", "C", "D"], moves = [1, 2, 0, 3], k = 1000000
Output: ["C", "A", "B", "D"]

Input:  line = [10, 20, 30, 40, 50], moves = [4, 3, 0, 1, 2], k = 5
Output: [50, 40, 10, 20, 30]

Constraints

• 0 <= n <= 10**5 and len(moves) == n
• moves holds each of 0 .. n - 1 exactly once.
• Names may repeat.
• 0 <= k <= 10**18
• Do not modify the inputs.
• Target: O(n) time, whatever the value of k.

Goals

• Split a permutation into cycles
• Jump k steps around each cycle using k modulo its length
• Avoid simulating an astronomically long routine