G. Greedy Merchants
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In a market, there are $$$N$$$ merchants numbered from $$$1$$$ to $$$N$$$ and $$$N$$$ items numbered from $$$1$$$ to $$$N$$$. Each merchant possesses an item. Initially, merchant $$$i$$$ owns item $$$i$$$.

Each item has a value $$$V_i$$$ and a cost $$$C_i$$$. A merchant who owns item $$$i$$$ is willing to trade it for another item $$$j$$$ if the value of item $$$j$$$ is greater than or equal to the cost of item $$$i$$$. A trade between two merchants is fair if both merchants involved are willing to trade their current item for another. Formally, a trade between the merchant who owns item $$$i$$$ and the merchant who owns item $$$j$$$ is fair if and only if $$$V_i\geq C_j$$$ and $$$V_j\geq C_i$$$. Upon a fair trade, the two merchants swap their items, while the values and costs of the items remain unchanged. Note that the value of an item may not necessarily be greater than its cost.

There are $$$Q$$$ independent queries from the merchants. In the $$$i$$$-th query, merchant $$$u$$$, who initially owns item $$$u$$$, wishes to obtain item $$$v$$$ through a sequence of fair trades. Hence, he would like to know whether it is possible for him to obtain item $$$v$$$ and, if so, the minimum number of trades required. Note that trades can occur between any pair of merchants, neither merchant $$$u$$$ nor merchant $$$v$$$ are necessarily involved in the trades. Since the queries are made before any trades begin, each query should be considered independently based on the initial state of the market.

Write a program to answer the queries made by the merchants.

Input

The first line contains an integer $$$N$$$ $$$(2\leq N\leq2\times10^5)$$$, the number of merchants.

The second line contains $$$N$$$ integers $$$V_i$$$ $$$(1\leq V_i \leq 10^9)$$$, the value of the $$$i$$$-th item.

The third line contains $$$N$$$ integers $$$C_i$$$ $$$(1\leq C_i \leq 10^9)$$$, the cost of the $$$i$$$-th item.

The fourth line contains an integer $$$Q$$$ $$$(1\leq Q\leq2\times10^5)$$$, the number of queries.

The next $$$Q$$$ lines contain the descriptions of the queries. The $$$i$$$-th of these lines contains two integers, $$$u$$$ and $$$v$$$ $$$(1\leq u,v \leq N)$$$. It is guaranteed that $$$u \neq v$$$.

Output

For each query, output a single line. If it is possible for merchant $$$u$$$ to obtain item $$$v$$$, output the minimum number of trades required. Otherwise, output -1.

Examples
Input
5
3 1 4 2 3
2 3 1 1 5
3
2 1
1 4
3 5
Output
2
1
-1
Input
5
9 3 7 10 5
4 1 3 6 9
2
1 2
2 5
Output
2
3
Note

In Sample 1, there are $$$5$$$ merchants and $$$3$$$ queries.

In the first query, merchant $$$2$$$ wishes to obtain item $$$1$$$. He can do so by first trading with merchant $$$3$$$, then trading with merchant $$$1$$$. Note that merchant $$$2$$$ cannot directly trade with merchant $$$1$$$ since $$$V_2 \lt C_1$$$. Hence, $$$2$$$ is the minimum number of trades required.

In the second query, merchant $$$1$$$ can directly trade with merchant $$$4$$$ to obtain item $$$4$$$. The minimum number of trades required is hence $$$1$$$.

In the third query, it can be proven that it is impossible for merchant $$$3$$$ to obtain item $$$5$$$ no matter how many trades are made.