URI Online Judge | 2735

Nina's Gift

By Giovanna Kobus Conrado, USP BR Brazil

Timelimit: 3

Nina got N distinct numbers from 0 to N-1 for Christmas. She realized that those numbers can be used to form a permutation: an array of size N in which all numbers from 0 to N-1 appears once. She then remembered that she had kept a very special permutation of size in her drawer, and she could use it to play with her new blocks. She came up with the following game:

At day 0, she will arrange the numbers in such a way that 0 is the fist one, 1 the second, and so on, until N-1, forming the array  V0. At day x, she will arrange the numbers to form the array Vx, in which Vx [ i ] = Vx-1 [ P [ i ] ], P being Nina's special permutation.

Her sister Nani got really jealous and decided to question Nina's knowledge about her permutation with questions of the following type: given two numbers J e K, what is the smallest number such that VY [ ( J + K ) % N ] = J ?

Help Nina with her sister's questions.

Input

The first line of input contains the number (t=10) of test cases.

Each case starts with a line containing a number (0<=N<=105): the number of blocks Nina got for Christmas. distinct integers ranging from 0 to N-1 follow.

The next line will contain an integer Q (1<=Q<=105): the number of questions Nani will ask, followed by Q lines, each containing two integers J and (0<=J,K<N).

Output

For each question, print the answer. If it does not exist, print -1.

Input Sample Output Sample

1

5

2 0 1 4 3

3

0 2

2 0

2 1

2

0

-1