Рассмотрим отрезок координатной прямой от \(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
3000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач