G. Смотровые башни
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим отрезок координатной прямой от $$$1$$$ до $$$n$$$. На этом отрезке стоят $$$k$$$ смотровых башен.

У каждой башни есть два параметра — координата $$$x_i$$$ и высота $$$h_i$$$. Все координаты башен различны. С башни $$$i$$$ можно увидеть точку $$$j$$$, если $$$|x_i - j| \le h_i$$$ (где $$$|a|$$$ — это абсолютное значение $$$a$$$).

За одну монету можно увеличить высоту любой башни на $$$1$$$. Увеличивать высоту каждой башни можно произвольное число раз (в том числе и ноль раз).

Надо обработать $$$q$$$ независимых запросов. В $$$i$$$-м запросе задаются две различных точки $$$l$$$ и $$$r$$$. Надо посчитать минимально необходимое количество монет, чтобы можно было увидеть обе эти точки (с одной башни или с разных башен).

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

В первой строке записаны два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le n$$$) — длина отрезка координатной прямой и количество смотровых башен.

Во второй строке записаны $$$k$$$ целых чисел $$$x_1, x_2, \dots, x_k$$$ ($$$1 \le x_i \le n$$$) — координаты смотровых башен. Все координаты башен различны.

В третьей строке записаны $$$k$$$ целых чисел $$$h_1, h_2, \dots, h_k$$$ ($$$0 \le h_i \le n$$$) — высоты смотровых башен.

В четвертой строке записано одно целое число $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — количество запросов.

В каждой из следующих $$$q$$$ строк записаны два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l < r \le n$$$) — описание очередного запроса.

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

На каждый запрос выведите одно целое число — минимально необходимое количество монет, чтобы можно было увидеть обе точки (с одной башни или с разных башен).

Примеры
Входные данные
20 3
2 15 10
6 2 0
3
1 20
10 11
3 4
Выходные данные
3 1 0
Входные данные
10 2
2 9
1 2
3
4 5
5 6
1 10
Выходные данные
2 2 0