15855번 - Permutation 다국어

A permutation P of size N is defined as an array [P₁, P₂, ..., P_N] where 1 ≤ P_i ≤ N and P_i ≠ P_j for i ≠ j.

We also define an order of a permutation. If A and B are permutations of size N, then A is less than B if and only if there exists an index i (1 ≤ i ≤ N) where:

• A_i < B_i, and
• A_j = B_j for all 1 ≤ j < i

We also define the multiplication of two permutations. If A and B are permutations of size N, then A × B is a permutation of size N, where the i-th element is A_Bi.

We also define the exponentiation of a permutation and a positive integer. If P is permutation and z is a positive integer, then P^z is defined as follow:

• P^z = P, for z = 1
• P^z = P^z-1 × P, for z > 1

You are given a permutation P of size N. Let M be the smallest integer greater than 1 such that P = P^M. We define A (index starts from 1) as an array consisting of Pⁱ for all 1 ≤ i < M sorted in the increasing order (of permutation). In other words, A_i < A_j for all 1 ≤ i < j < M.

For example, suppose P = [2,3,1,5,4]. Therefore:

• P¹ = [2,3,1,5,4],
• P² = [3,1,2,4,5],
• P³ = [1,2,3,5,4],
• P⁴ = [2,3,1,4,5],
• P⁵ = [3,1,2,5,4],
• P⁶ = [1,2,3,4,5],
• P⁷ = [2,3,1,5,4].

Thus, the value of M in this case is 7, and A = [P⁶, P³, P⁴, P¹, P², P⁵].

You are also given Q queries. The i-th query contains an integer K_i. The answer for the i-th query is an integer T_i such that 1 ≤ T_i < M and P^T_i = A_Ki. Can you answer all of the queries?

The first line contains two integers: N Q (1 ≤ N ≤ 100; 1 ≤ Q ≤ 300,000) in a line denoting the size of the permutation and the number of queries. The second line contains N integers: P₁ P₂ ... P_N (1 ≤ P_i ≤ N) in a line denoting the permutation. It is guaranteed that for P_i ≠ P_j all i ≠ j. The next Q lines, each contains an integer; the integer on the i-th line is K_i (1 ≤ K_i < M, where M is the smallest integer greater than 1 such that P = P^M as explained above. Note that M is not explicitly given in this problem) denoting the query.

Q lines, each contains an integer: T_i in a line denoting the answer of the i-th query.

Explanation for the 1st sample case

The permutation given in the first sample is the same as the permutation given in the problem description.