Cycle detection P30452

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),\ \dots,\ x_k=f(x_{k-1}),\ \dots$ eventually repeats some values, i.e., there is some $i \ge 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$:

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 \le n \le 10^5$ and $0 \le k \le 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.