E. Отдыхаем группами
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Один очень известный клуб «по интересам» собирает своих членов на отдых на природе. Чтобы мероприятие было интересней, директора клуба решили разбить членов клуба на группы.

Каждый человек характеризуется двумя целыми числами: ri — ответственность, ai — возраст. Группой назовем непустое подмножество членов клуба с одним особенным членом клуба, которого мы будем называть лидером группы. Лидер группы должен быть одним из самых ответственных людей в группе (его ответственность должна быть не меньше, чем у любого другого человека из группы), также возраст любого человека в группе должен отличаться не более чем на k от возраста лидера группы.

Некоторые члены клуба друзья, поэтому они хотят попасть в одну группу. Конечно же, интересней отдыхать в группе с большим количеством людей. Поэтому администрация клуба просит Вас написать программу, которая будет отвечать на следующий запрос: «Какой наибольший размер может быть у группы, которая содержит одновременно человека x и человека y?». Возможно, x или y будет лидером этой группы.

Входные данные

В первой строке записано два целых числа n и k (2 ≤ n ≤ 105, 0 ≤ k ≤ 109) — количество членов клуба и возрастное ограничение для группы.

В следующей строке записаны целые числа r1, r2, ..., rn (1 ≤ ri ≤ 109), разделенные пробелами, — ответственности людей. В следующей строке в таком же формате записаны целые числа a1, a2, ..., an (1 ≤ ai ≤ 109) — возрасты людей.

В следующей строке записано единственное целое число q (1 ≤ q ≤ 105) — количество запросов. В следующих q строках записаны запросы в виде пар целых чисел, разделенных пробелом, xi и yi (1 ≤ xi, yi ≤ n, xi ≠ yi) — номера людей, которые должны оказаться в одной группе.

Выходные данные

Для каждого запроса выведите ответ в отдельной строке — максимальное количество людей в группе, которая содержит заданных людей. Если такой группы не существует, выведите -1.

Примеры
Входные данные
5 1
1 5 4 1 2
4 4 3 2 2
4
5 3
2 3
2 5
4 1
Выходные данные
4
3
-1
4
Примечание

В первом запросе самая большая группа, включающая участников 3 и 5 — это группа {1, 3, 4, 5}, где 3 является лидером группы.

Во втором запросе лидером должен быть участник 2, так, что группа будет иметь следующий состав: {1, 2, 3}.

В третьем запросе у лидера группы должен быть возраст 3. Следовательно, единственным лидером может быть участник 3, но он менее ответственный, чем участник 2. Таким образом, сформировать такую группу невозможно.

В четвертом запросе группа такая же, как и в первом.