Туристическая отрасль в этом сезоне столкнулась с серьёзными сложностями. Добросовестные туроператоры ищут новые рекламные ходы для продажи своих туров. Как известно, наиболее благоприятная для отдыха погода меняется плавно, причём не только от одного дня к другому, но и в течение суток.
Для большинства туристических направлений есть многолетние посекундные результаты измерений различных климатических параметров, например, температуры или влажности. У каждого человека своё понимание того, насколько различными могут быть подобные значения во время отпуска, но всех интересуют непрерывные туры как можно большей продолжительности.
Пусть мы зафиксировали туристическое направление и некоторый климатический параметр. Будем называть изменчивостью тура разницу между максимальным и минимальным значением выбранного параметра за всё время поездки. Для каждого туриста известно максимальное приемлемое значение изменчивости 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