Powers of permutations X39049

Given an n, a permutation of {0, 1, … n−1} is a sequence where each of the numbers 0, 1, … n−1 occurs exactly once. For example, if n = 3, the sequences (1 2 0), (2 0 1) and (0 1 2) are permutations of {0, 1, 2}.

Given two permutations σ = (σ₀, …, σ_n−1) and τ = (τ₀, …, τ_n−1) of {0, 1, … n−1 }, their product σ ∘ τ is defined as the permutation ρ = (ρ₀, …, ρ_n−1) such that ρ_i = σ_τi. For example, if n = 3, σ = (1 2 0) and τ = (2 0 1), then σ ∘ τ = (0 1 2), since:

• τ₀ = 2 and σ₂ = 0,
• τ₁ = 0 and σ₀ = 1, and
• τ₂ = 1 and σ₁ = 2.

Make a program that, given a permutation σ and a natural k, computes the power of σ raised to k: σ^k = σ ∘ … ∘ σ^k). By convention, σ⁰ = (0, 1, …, n−1).

Input

The input includes several cases. Each case consists in the number n (1 ≤ n ≤ 10⁴), followed by n numbers between 1 and n that describe the permutation σ, followed by the number k (0 ≤ k ≤ 10⁹).

Output

Write the permutation σ^k.

Observation

The expected solution to this problem has cost O(n · logk). The solutions that have cost Ω(n · k) can get at most 3 points over 10.

You can add (few) lines of comments explaining what you intend to do.

If needed, you can use that the product of permutations is associative.