Бизон-Чемпион недавно закончил покраску своего забора. Забор представляет из себя последовательность из n досок ширины 1 метр и произвольной высоты. i-я доска имеет высоту hi метров. Соседние доски следуют без зазора.
После покраски Бизон-чемпион решил разместить на заборе объявление о его продаже. Объявление будет выполнено на листе бумаги прямоугольного размера и расположено на заборе так, что боковые стороны листа параллельны доскам забора, и края листа совмещены с краями некоторых досок. Бизон-Чемпион ввел для себя следующие ограничения на размещение объявления:
- Ширина объявления после размещения должна быть ровно w метров.
- Объявление должно целиком находиться на участке забора с l-й по r-ю доски включительно (в том числе, нельзя выходить за пределы забора по вертикали).
Объявление будет красочным, поэтому Бизон-чемпион хочет, чтобы высота объявления была как можно больше.
Вам дано описание забора и несколько запросов на размещение объявления. Для каждого запроса выведите максимальную возможную высоту объявления, которое можно разместить на соответствующем участке забора при заданной фиксированной ширине объявления.
Выходные данные
На каждый запрос выведите ответ в отдельной строке — максимальную высоту объявления, которую можно достичь на соответствующем участке забора при соблюдении всех условий.
Примечание
Забор, описанный в примере, выглядит следующим образом:
Ниже приведены возможные расположения объявлений при ответе на запросы.
Расположение объявления при ответе на первый запрос. 
Расположение объявления при ответе на второй запрос. 
Расположение объявления при ответе на третий запрос.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2 2 3 3
3
2 5 3
2 5 2
1 5 5
|
2
3
1
|