Недавно Василько на день святого Миколая отримав подарунки. Одним з тих подарунків був масив довжини . Також він отримав робота, котрий працює на масиві.
Якщо робот має оперативну пам'ять розміру , то він може запам'ятати не більше ніж чисел. Робота можна запустити на масиві, і він з елементів цього масиву сконструює новий масив , який буде лексикографічно^{*} найменший з усіх можливих, використовуючи такі операції в довільному порядку:
Якщо кількість вільних місць в оперативній пам'яті не менша від одиниці, тоді помістити в неї число на позиції і перейти на позицію i+1.
Якщо оперативна пам'ять не пуста, то записати довільне число в масив та видалити його з оперативної пам'яті.
Васильку стало цікаво, яким буде -те число в масиві , якщо робот має оперативну пам'ять розміру та запустить його на підмасиві від до . Йому дуже подобається масив , тому він не хоче запускати робота на ньому і просить вас відповісти на запитань, що назбиралися в нього за цей тиждень.
^{*}Масив є лексикографічно меншим за масив , якщо в першому моменті, коли відмінний від , в масиві значення менше ніж в масиві .
Перший рядок містить два цілі числа та (1 \le n \le 10^5, 1 \le q \le 2\cdot10^5) — довжина масиву і кількість запитань.
Другий рядок містить цілих чисел a_{1}, a_{2}, \dots, a_{n} (0 \le a_{i} \le 10^9) — значення масиву .
Кожен з наступних рядків містить чотири цілі числа , , та (1 \le m \le n, 1 \le l \le r \le n, 1 \le k \le r - l + 1) — два кінці підмасиву, розмір оперативної пам'яті та індекс числа, котре цікаве Васильку.
Для кожного запитання в окремому рядку випишіть відповідь на нього.
Example 1
В першому запитані найменший лексигографічний масив має вигляд , на третьому місці стоїть . Найменші лексикографічні масиви в наступних запитах будуть такими:
( балів): для всіх запитань m = n, l = 1, r = n;
( балів): сума довжин всіх запитань не перевищує 10^6;
( балів): для всіх запитань k + m \le 30;
( балів): для всіх запитань m = n і n, q \le 10^3;
( балів): для всіх запитань m = n і q \le 10^5;
( балів): для всіх запитань m = n;
( балів): a_{i} \le 30;
( балів): n \le 10^3;
( балів): q \le 10^5;
( балів): без додаткових обмежень.