For any function f that maps a finite set to itself, and for any initial value
x_{0} in the set, the sequence of values x_{0}, x_{1}=f(x_{0}), x_{2}=f(x_{1}),
…, x_{k}=f(x_{k−1}), … eventually repeats some values, i.e., there is
some i ≥ 0 and some j > i such that f(x_{j}) = f(x_{i}). Once this happens, the
sequence continues by repeating the cycle from x_{i} to x_{j−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 x_{0} = 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 j−i=3.

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

Input

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

Output

For every case, print its number and k lines each one with j−i 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++