Cycle detection P30452

For any function f that maps a finite set to itself, and for any initial value x₀ in the set, the sequence of values x₀, x₁=f(x₀), x₂=f(x₁), …, 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₀ = 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₀, 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⁵ and 0 ≤ k ≤ 10n. Follow, in order, the n images of the numbers in [0, n−1]. Follow k ‍numbers: the x₀’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.