I. Balto's Training
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Balto is a Siberian Husky who is getting ready to compete in the Great Alaskan Sled Dog Race. The Great Alaskan Sled Dog Race is a grueling competition that takes place over several days. During the race, teams of sled dogs traverse a treacherous path through snow-covered terrain. As a result, he will need to train hard.

In preparation for the race, Balto is practicing in an area that consists of $$$N$$$ villages numbered from $$$1$$$ to $$$N$$$. Each village has a "left" and "right" trail leading to another checkpoint.

Balto has a peculiar way of practicing: he starts at a village and runs $$$K$$$ times to the left, then $$$K$$$ times right, $$$K$$$ times left again, and finally $$$K$$$ times to the right again.

Your task is to help Balto answer $$$Q$$$ queries about where he will end up after completing the course. Each query contains two integers, the starting village and the number of times $$$K$$$ that he will go left or right.

Given the village's left and right path destinations as well as a series of queries, help Balto determine where he will end up, for each query.

Input

The first line of input contains an integer $$$N$$$ $$$(1 \le N \le 10^5)$$$ - the number of villages on the path.

Each of the next $$$N$$$ lines contains two integers, the indices of the villages on the "left" and "right" trails respectively.

The next line contains an integer $$$Q$$$ $$$(1 \le Q \le 10^5)$$$ - the number of queries.

Each of the next $$$Q$$$ lines contains two integers, the starting village and the number of times $$$K$$$ ($$$1 \leq K \leq 10^9$$$) Balto must run the course.

Output

For each query, print a single integer denoting the village where Balto will end up after completing the course.

Example
Input
3
2 3
3 1
1 3
3
1 1
1 2
3 1
Output
1
3
3