Camping Groups

Description:

Input:

The first line contains two integers n and k (2 ≤ n ≤ 10⁵, 0 ≤ k ≤ 10⁹) — the number of club members and the age restriction for one group.

The next line contains integer numbers r₁, r₂, ..., r_n (1 ≤ r_i ≤ 10⁹) separated by space: r_i denotes the i-th club member's responsibility. In the same way there are integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹) in the third line: a_i denotes the i-th club member's age.

The next line contains an integer q denoting the number of questions that you should answer (1 ≤ q ≤ 10⁵). The next q lines describe the questions. Each line contains two space-separated integers x_i and y_i (1 ≤ x_i, y_i ≤ n, x_i ≠ y_i) — the indices of the club members that should end up in the same group.

Output:

For each question print the maximum size of the group in a line. If making such a group is impossible print -1 instead.

Sample Input:

5 1
1 5 4 1 2
4 4 3 2 2
4
5 3
2 3
2 5
4 1

Sample Output:

4
3
-1
4

Note:

In the first query the largest group with members 3 and 5 is {1, 3, 4, 5} where member 3 is the leader.

In the second query member 2 should be the leader so the group will be {1, 2, 3}.

In the third query the leader of the group should have age 3 so the only leader can be member 3, who is less responsible than member 2. So making a group is impossible.

The group for the fourth query is the same as first query.