Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Camping Groups

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputA club wants to take its members camping. In order to organize the event better the club directors decided to partition the members into several groups.

Club member *i* has a responsibility value *r*_{i} and an age value *a*_{i}. A group is a non-empty subset of club members with one member known as group leader. A group leader should be one of the most responsible members of the group (his responsibility value is not less than responsibility of any other group member) and his age absolute difference with any other group member should not exceed *k*.

Some club members are friends and want to be in the same group. They also like their group to be as large as possible. Now you should write a program that answers a series of questions like "What's the largest size of a group containing club member *x* and club member *y*?". It's possible for *x* or *y* to be the group leader.

Input

The first line contains two integers *n* and *k* (2 ≤ *n* ≤ 10^{5}, 0 ≤ *k* ≤ 10^{9}) — the number of club members and the age restriction for one group.

The next line contains integer numbers *r*_{1}, *r*_{2}, ..., *r*_{n} (1 ≤ *r*_{i} ≤ 10^{9}) separated by space: *r*_{i} denotes the *i*-th club member's responsibility. In the same way there are integers *a*_{1}, *a*_{2}, ..., *a*_{n} (1 ≤ *a*_{i} ≤ 10^{9}) 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^{5}). 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.

Examples

Input

5 1

1 5 4 1 2

4 4 3 2 2

4

5 3

2 3

2 5

4 1

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.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/14/2021 05:17:45 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|