Alice and Bob are playing with a magic tree This magic tree has
Input contains multiple tests
The first line contains one integer
The following lines describe all the test cases
For each test case: The first line contains an integer
The second line has
The third row has
In the fourth line, a number
The next
First a number
If
If
For each query with
1 4 1 2 3 1 1 1 1 3 1 4 2 3 2 1 4
4 3 Hint For the first query: 4-\>3-\>2-\>1-\>out For the second query:4-\>3-\>1-\>out