E. Интеллектуальный отпуск
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
e.in
вывод
e.out

Туристическая отрасль в этом сезоне столкнулась с серьёзными сложностями. Добросовестные туроператоры ищут новые рекламные ходы для продажи своих туров. Как известно, наиболее благоприятная для отдыха погода меняется плавно, причём не только от одного дня к другому, но и в течение суток.

Для большинства туристических направлений есть многолетние посекундные результаты измерений различных климатических параметров, например, температуры или влажности. У каждого человека своё понимание того, насколько различными могут быть подобные значения во время отпуска, но всех интересуют непрерывные туры как можно большей продолжительности.

Пусть мы зафиксировали туристическое направление и некоторый климатический параметр. Будем называть изменчивостью тура разницу между максимальным и минимальным значением выбранного параметра за всё время поездки. Для каждого туриста известно максимальное приемлемое значение изменчивости ki.

Даны результаты измерений некоторого климатического параметра на одном из курортов и значения ki для нескольких туристов. Требуется для каждого из них определить максимальный диапазон, подходящий для отпуска.

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

В первой строке входного файла находится целое число N (1 ≤ N ≤ 600 000) — количество сделанных измерений. Во второй строке — N целых чисел, по модулю не превосходящих 109 — данные посекундных измерений.

В третьей строке входного файла находится число M (1 ≤ M ≤ 100) — количество туристов, для которых необходимо найти оптимальный диапазон. В четвёртой строке — M целых чисел k1, k2, ..., kM (0 ≤ ki ≤ 109) — максимальная возможная разница между выбранным климатическим параметром в непрерывном диапазоне дней для каждого из туристов.

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

В выходной файл для каждого из M запросов в отдельной строке выведите два числа: номер первого измерения диапазона и номер последнего измерения, входящего в диапазон. Нумерация измерений ведётся с единицы. Если для некоторого туриста существует несколько подходящих диапазонов максимальной длины, выведите границы любого из них.

Примеры
Входные данные
7
10 1 10 12 11 1 11
2
2 1
Выходные данные
3 5
4 5