By Giovanna Kobus Conrado, USP Brazil
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 N 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 Y such that VY [ ( J + K ) % N ] = J ?
Help Nina with her sister's questions.
The first line of input contains the number t (t=10) of test cases.
Each case starts with a line containing a number N (0<=N<=105): the number of blocks Nina got for Christmas. N 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 K (0<=J,K<N).
For each question, print the answer. If it does not exist, print -1.
|Input Sample||Output Sample|
2 0 1 4 3