# Cycle detection P30452

Statement html

For any function f that maps a finite set to itself, and for any initial value x0 in the set, the sequence of values x0, x1=f(x0), x2=f(x1), …, xk=f(xk−1), … eventually repeats some values, i.e., there is some i ≥ 0 and some j > i such that f(xj) = f(xi). Once this happens, the sequence continues by repeating the cycle from xi to xj−1.

For instance, the function that maps (0,1,2,3,4,5,6,7,8) to (6,6,0,1,4,3,3,4,0) generates the following sequence when x0 = 2:

2   0   6   3   1   6   3   1   6   3   1   …

In this sequence, the beginning of the cycle (6 3 1) is found after 2 steps. In this case, i=2, j=5, and the periodicity is ji=3.

Given a function that maps the interval [0, n−1] to itself, and several starting values x0, compute the corresponding values of ji and i.

Input

Input starts with the number of cases. Every such case begins with two integer numbers 1 ≤ n ≤ 105 and 0 ≤ k ≤ 10n. Follow, in order, the n images of the numbers in [0, n−1]. Follow k numbers: the x0’s for which the result must be computed.

Output

For every case, print its number and k lines each one with ji and i.

Observation

Since some of the private cases are huge, a recursive program may exhaust the recursion stack.

Public test cases
• Input

```3
9 1
6 6 0 1 4 3 3 4 0
2
3 3
2 1 0
0 1 2
4 3
1 2 3 2
1 0 1
```

Output

```Case #1:
3 2
Case #2:
2 0
1 0
2 0
Case #3:
2 1
2 2
2 1
```
• Information
Author
Xavier Martínez
Language
English
Official solutions
C++
User solutions
C++