Туристическая отрасль в этом сезоне столкнулась с серьёзными сложностями. Добросовестные туроператоры ищут новые рекламные ходы для продажи своих туров. Как известно, наиболее благоприятная для отдыха погода меняется плавно, причём не только от одного дня к другому, но и в течение суток.
Для большинства туристических направлений есть многолетние посекундные результаты измерений различных климатических параметров, например, температуры или влажности. У каждого человека своё понимание того, насколько различными могут быть подобные значения во время отпуска, но всех интересуют непрерывные туры как можно большей продолжительности.
Пусть мы зафиксировали туристическое направление и некоторый климатический параметр. Будем называть #cf_span(class=[tex-font-style-underline], body=[изменчивостью]) тура разницу между максимальным и минимальным значением выбранного параметра за всё время поездки. Для каждого туриста известно максимальное приемлемое значение изменчивости ki.
Даны результаты измерений некоторого климатического параметра на одном из курортов и значения ki для нескольких туристов. Требуется для каждого из них определить максимальный диапазон, подходящий для отпуска.
В первой строке входного файла находится целое число N (1 ≤ N ≤ 600 000) — количество сделанных измерений. Во второй строке — N целых чисел, по модулю не превосходящих 109 — данные посекундных измерений.
В третьей строке входного файла находится число M (1 ≤ M ≤ 100) — количество туристов, для которых необходимо найти оптимальный диапазон. В четвёртой строке — M целых чисел k1, k2, ..., kM (0 ≤ ki ≤ 109) — максимальная возможная разница между выбранным климатическим параметром в непрерывном диапазоне дней для каждого из туристов.
В выходной файл для каждого из M запросов в отдельной строке выведите два числа: номер первого измерения диапазона и номер последнего измерения, входящего в диапазон. Нумерация измерений ведётся с единицы. Если для некоторого туриста существует несколько подходящих диапазонов максимальной длины, выведите границы любого из них.
## Входные Данные
В первой строке входного файла находится целое число N (1 ≤ N ≤ 600 000) — количество сделанных измерений. Во второй строке — N целых чисел, по модулю не превосходящих 109 — данные посекундных измерений.В третьей строке входного файла находится число M (1 ≤ M ≤ 100) — количество туристов, для которых необходимо найти оптимальный диапазон. В четвёртой строке — M целых чисел k1, k2, ..., kM (0 ≤ ki ≤ 109) — максимальная возможная разница между выбранным климатическим параметром в непрерывном диапазоне дней для каждого из туристов.
## Выходные Данные
В выходной файл для каждого из M запросов в отдельной строке выведите два числа: номер первого измерения диапазона и номер последнего измерения, входящего в диапазон. Нумерация измерений ведётся с единицы. Если для некоторого туриста существует несколько подходящих диапазонов максимальной длины, выведите границы любого из них.
## Примеры
Входные данные710 1 10 12 11 1 1122 1Выходные данные3 54 5
[samples]
**Definitions**
Let $ N \in \mathbb{Z}^+ $ be the number of measurements.
Let $ A = (a_1, a_2, \dots, a_N) $ be a sequence of integers, where $ |a_i| \leq 10^9 $ for all $ i \in \{1, \dots, N\} $.
Let $ M \in \mathbb{Z}^+ $ be the number of tourists.
Let $ K = (k_1, k_2, \dots, k_M) $ be a sequence of non-negative integers, where $ k_j \in [0, 10^9] $ for all $ j \in \{1, \dots, M\} $.
**Constraints**
1. $ 1 \leq N \leq 600{,}000 $
2. $ 1 \leq M \leq 100 $
3. $ |a_i| \leq 10^9 $ for all $ i \in \{1, \dots, N\} $
4. $ 0 \leq k_j \leq 10^9 $ for all $ j \in \{1, \dots, M\} $
**Objective**
For each tourist $ j \in \{1, \dots, M\} $, find a contiguous subarray $ A[i..l] = (a_i, a_{i+1}, \dots, a_l) $, with $ 1 \leq i \leq l \leq N $, such that:
$$
\max_{p \in [i,l]} a_p - \min_{p \in [i,l]} a_p \leq k_j
$$
and the length $ l - i + 1 $ is maximized.
Output the pair $ (i, l) $ — the 1-based indices of the first and last measurement of such a subarray.
If multiple such subarrays exist, output any one.