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* ≤ 10*n*.
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++
- Event
- Setè Concurs de Programacio de la UPC - Final
- Date
- 2009-09-16