Permutation (Problem K, 2017 ICPC Asia Jakarta Regional Contest, 2017)
Time limit: 3 sec
Memory limit: 256MB
Author: Ivan Adrian Koswara

# Problem Statement

A permutation $P$ of size $N$ is defined as an array $[P_1, P_2, \cdots, P_N]$ where $1 \le P_i \le N$ and $P_i \ne P_j$ for $i \ne 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 \le i \le N$) where:

- $A_i < B_i$, and  
- $A_j = B_j$ for all $1 \le j < i$

We also define the multiplication of two permutations. If $A$ and $B$ are permutations of size $N$, then $A \times B$ is a permutation of size $N$, where the $i$-th element is $A_{B_i}$.

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} \times 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^i$ for all $1 \le i < M$ sorted in increasing order (of permutation). In other words, $A_i < A_j$ for all $1 \le i < j < M$.

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

- $P^1 = [2,3,1,5,4]$  
- $P^2 = [3,1,2,4,5]$  
- $P^3 = [1,2,3,5,4]$  
- $P^4 = [2,3,1,4,5]$  
- $P^5 = [3,1,2,5,4]$  
- $P^6 = [1,2,3,4,5]$  
- $P^7 = [2,3,1,5,4]$

Thus, the value of $M$ in this case is $7$, and $A = [P^6, P^3, P^4, P^1, P^2, P^5]$.

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 \le T_i < M$ and $P^{T_i} = A_{K_i}$. Can you answer all of the queries?

# Input

The first line contains two integers: $N \ Q$ ($1 \le N \le 100$; $1 \le Q \le 300,000$) in a line denoting the size of the permutation and the number of queries.  
The second line contains $N$ integers: $P_1\ P_2\ \cdots\ P_N$ ($1 \le P_i \le N$) in a line denoting the permutation.  
It is guaranteed that $P_i \ne P_j$ for all $i \ne j$.  
The next $Q$ lines, each contains an integer; the integer on the $i$-th line is $K_i$ ($1 \le 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 the problem) denoting the query.

# Output

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

# Sample Input
```
5 6
2 3 1 5 4
1
2
3
4
5
6
```
# Output for Sample Input
```
6
3
4
1
2
5
```
# Explanation for the 1st sample case

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


Sample inputs:
5 6
2 3 1 5 4
1
2
3
4
5
6

Sample outputs:
6
3
4
1
2
5

# Solution Analysis
Analysis author: Ivan Adrian Koswara

For convenience, we will define $I$ to be the identity permutation, redefine $M$ to be the smallest positive integer such that $P^M = I$ (instead of $P^M = P$), and redefine $K$ to be one less than the input (in other words, we number the permutations in the list as $0, 1, 2, \ldots, M-1$ instead of $1, 2, 3, \ldots, M$).

One very important observation about permutations is that we can decompose it into disjoint cycles. For example, the permutation $[2, 4, 5, 1, 3]$ is made of two cycles: $(1, 2, 4)$ and $(3, 5)$. (The cycle $(1, 2, 4)$ means 1 maps to 2, 2 maps to 4, and 4 maps back to the beginning of the cycle 1.) Then, when we raise a permutation to the $T$-th power, we're simply raising each cycle into the $T$-th power, and it's easy to raise a cycle to the $T$-th power; given a cycle $(A_0, A_1, \ldots, A_{L-1})$, if we raise it to the $T$-th power, element $A_i$ will now be mapped to $A_{(i+T)\bmod L}$.

The first question is, what is the value of $M$? Note that if we raise a cycle of length $L$ to the $L$-th power, it will become the identity; all elements are mapped to themselves. And moreover, only multiples of $L$ will bring this cycle to the identity. Thus, for every cycle in $P$ of length $L$, we need $L$ to divide $M$, otherwise this cycle won't become the identity. Thus we need $M$ to be a multiple of the $\text{LCM}$ of all cycle lengths. Conversely, taking $M$ to be this $\text{LCM}$ is enough.

Can we simply make the list of all permutations and sort it? As it turns out, no, since $M$ can be as large as $232{,}792{,}560$. So we need to obtain the value of $T$ for each $K$ directly without sorting the list of permutations.

Since we're sorting in lexicographic order, the initial elements matter the most. The list will begin with those where the first element is 1, followed by those where the first element is 2, then those where the first element is 3, and so on. The important thing is to be able to compute, exactly how many permutations begin with a specific first element.

Consider the cycle containing the first element. Only these elements will ever possibly appear as the first element. For example, if the cycle is $(1, 2, 4)$ like in the example above, then only 1, 2, 4 can possibly be the first element; it will never be 3 or 5. Moreover, for each element that can possibly appear, they will all appear the same number of times; this is easy to see by checking that $P^1, P^2, P^3, \ldots, P^M$ cycles the first element. This means we can easily fix the first element. Suppose the cycle containing the first element has length $L$, and let $X = M/L$. Then take $K = YX + Z$ where $0 \leq Z < X$. This means we skip the first $Y$ candidates (from smallest to largest), then take the next candidate as the first element. Moreover, from the rest of the elements, we're trying to find the $Z$-th permutation made from them.

For example, consider our example $[2, 4, 5, 1, 3]$; we have $M = 6$ and $L = 3$, so $X = 2$. Let $K = 4$ (the input is 5); then $Y = 2$ and $Z = 0$. So we skip the first $Y = 2$ possibilities of the first element, and take the next one. That is, we skip 1 and 2, and take 4 as the first element of the permutation. And moreover, we're looking for the $0$-th (remember, zero-indexed) permutation that begins with the element 4.

We can in fact continue this way, but we need to be careful. After we fix the first element, the entire cycle containing it is also fixed. Moreover, for the later elements, there might be elements that end up impossible. For example, consider the permutation $[2, 1, 4, 5, 6, 3]$. Here we have $M = 4$. If the first element turns out to be 2, then the third element can only be 4 or 6; it's impossible to get 3 or 5. Conversely, if the first element is 1, then the third element can only be 3 or 5, not 4 or 6.

By carefully walking through the elements of the permutation, it's possible to obtain a solution in $O(N^2)$ per query. But this is not fast enough; we will need to do some preprocessing so we can improve this solution.

The idea is to store which possibilities are possible for each element, and how it affects the future elements. For example, in the example $[2, 1, 4, 5, 6, 3]$, the first element has possibilities $\{1, 2\}$. This will completely fix the second element; moreover, if 1 is chosen, then the third element has possibilities $\{3, 5\}$, while if 2 is chosen, then the third element has possibilities $\{4, 6\}$. Not only that, we add some other information: if 1 was chosen, then $T = 0 \bmod 2$ (we need an even $T$ in order for $P^T$ to have 1 at first element), and if 2 was chosen, then $T = 1 \mod 2$. And similarly, if 3, 4, 5, 6 are chosen as the third element, then $T = 0, 1, 2, 3 \mod 4$ respectively.

If we have all this information, we can solve a query in $O(N)$ time. Given an input $K$, we first decompose it as $YX + Z$ as above. The value of $Y$ will decide which element is the first element, and what congruence relation that $T$ must satisfy; the value of $Z$ will be passed down the permutation. Using this first element, we can decide which list of possibilities we look at using $Z$, we can decide which element actually goes in that position.

In our example above, the third element has possibilities $\{3, 5\}$ (if the first element is 1) or $\{4, 6\}$ (if the first element is 2). Suppose the first element is 1, and $Z = 1$. Then we look at the list $\{3, 5\}$, and take the 1-th (zero-indexed) smallest element; that is, 5 goes to the third element. If instead the first element was 2 but with same $Z$, we would have taken 6 instead.

We will be able to reconstruct the permutation in $O(N)$ time, and along the way we obtain several congruence relations for $T$. There are at most $N$ of them (in fact, more careful analysis says that there are at most $O(\sqrt{N})$ of them, but we don't need it). Using Chinese Remainder Theorem, we can combine a pair of congruence relations into one in time $O(\log N)$ assuming there is no overflow, so in total we can combine all congruence relations into one in time $O(N \log N)$. Thus the total time per query would be $O(N \log N)$, which passes under the limit.

The problem is, how do we preprocess the permutation? The idea is to compute how much of the permutation has been fixed so far. Before we fix the first element, $T$ can still be anything. After we fix the first element, whose cycle has length $L$, we would know the value of $T \mod L$ in the queries. Suppose we have a later cycle of length $L'$, and $\gcd(L, L') = G$. Then we would also know the value of $T \mod G$, since we know the value of $T \mod L$. This means the first element on this later cycle is somewhat fixed, since we already know the value of $T \mod G$; there are less degrees of freedom.

This is exhibited in the above example, $[2, 1, 4, 5, 6, 3]$. The first cycle $(1, 2)$ has length 2; this is $L$. The second cycle $(3, 4, 5, 6)$ has length 4; this is $L'$. Whatever the value of $T$ will end up to be, by inspecting $K$ we will know what the first element is, and hence the value of $T \mod L = T \mod 2$. But this means the second cycle is not fully free; we know the value of $T \mod 2$, and so not all possibilities for the second cycle remain. For example, if we have $T \mod 2 = 0$, it's impossible to have $T \mod 4 = 1$; the value of $T \mod 4$ will only be either 0 or 2. As we see before, a starting element of 1 means the second cycle can only start with 3 or 5, not 4 or 6; this is where this observation occurs.

Thus, the idea is to keep track this modulo over the permutation. After preprocessing the $i$-th element, the value of $T$ is fixed modulo $B$ for some $B$. After looking at the next $(i+1)$-th element, it belongs in a cycle of length $L$; assume this is not a cycle that includes an earlier element (if it was, then we would have fixed the cycle). Define $G = \gcd(B, L)$; then we can partition the possibilities for the $(i+1)$-th element into $G$ groups; one for $T = 0 \mod G$, one for $T = 1 \mod G$, and so on. Each of these groups forms a list. The example above had the groups $\{3, 5\}$ and $\{4, 6\}$ for the third element, obtained when $T = 0 \mod 2$ and $T = 1 \mod 2$ respectively. Partitioning the list is easy; simply check which element will occupy this $(i+1)$-th position when we raise $P$ to the $1$-st, $2$-nd, $3$-rd, $\ldots$, $L$-th power; if an element $X$ occupies it when $P$ is raised to the $Y$-th power, then $X$ goes into the list $T = Y \mod G$. Finally, after we partition all the elements, the new value of $B$ is $\text{lcm}(B, L)$; the value of $T$ is now fixed that much.

This preprocessing in fact takes the same time $O(N \log N)$ as the time per query; most of the time is taken by computing the value of $G$, while partitioning the elements into lists takes only linear time. And given the above information, we can solve each query in $O(N \log N)$ time as described, which passes under the time limit.

Special judge (C++ scorer):