3. Vystupovanie

Každý víkend sa Jozef Hovnivál potreboval dostať domov z rodinného výmetu, aby si mohol sadnúť na svoju pohodlnú stolicu. Chodieval autotrusom. No aby to nemal také jednoduché, zakaždým sa rozhodol, akú dlhú prechádzku si chce spraviť domov z autotrusovej zastávky. Teda vystúpil na takej zastávke, ktorá je od jeho domu v správnej vzdialenosti. No toto ho rýchlo omrzelo, pretože chodil často tou istou trusou. Tak si vymyslel ešte jednu podmienku, a to že nepôjde z ktorejkoľvek zastávky, ktorá je v správnej vzdialenosti, ale z \(k\)-tej takej v poradí. Teda napríklad sa mohol rozhodnúť, že vystúpi na tretej zastávke, z tých, ktoré sú od jeho domu vzdialené 7 metrov. Jozefovi Hovniválovi ale zaberalo veľmi veľa času zistiť, na ktorej zastávke má vystúpiť. Preto potrebuje vašu pomoc.

Úloha

Na vstupe dostanete \(n\) čísel v rozsahu od \(1\) po \(1\,000\,000\). Toto sú vzdialenosti jednotlivých zastávok od jeho domu, v takom poradí, v akom ich prejde autotrus. Potom dostanete \(q\) otázok. Každá otázka pozostáva z čísla zastávky \(l\), na ktorej Jozef nastúpi, čísla zastávky \(r\), na ktorej mu skončí platnosť lístka (a teda nemôže pokračovať ďalej v ceste autotrusom). Ďalej dostanete dĺžku prechádzky \(v\), ktorú si Jozef praje a nakoniec na koľkej takej zastávke chce Jozef vystúpiť, \(k\). Vašou úlohou je vypísať číslo zastávky, ktorá sa nachádza v intervale od \(l\) po \(r\) vrátane, jej vzdialenosť od domu je \(v\) a je to \(k\)-ta taká zastávka v danom intervale. Ak taká neexistuje, vypíšte \(-1\). Číslujeme od jednotky.

Formát vstupu

Na prvom riadku vstupu sa nachádzajú čísla \(n\) a \(q\) oddelené medzerou, počet zastávok a počet otázok. Na druhom riadku sa nachádza \(n\) čísel oddelených medzerami, vzdialenosti zastávok od Jozefovho domu. Nasleduje \(q\) riadkov, na každom z ktorých sa nachádzajú medzerami oddelené čísla \(l\), \(r\), \(v\) a \(k\), ktorých význam je vysvetlený vyššie.

Formát výstupu

Vypíšte \(q\) riadkov výstupu. Na \(i\)-tom riadku sa nachádza odpoveď na \(i\)-tu otázku, teda číslo zastávky, ktorá spĺňa požadované vlastnosti, alebo \(-1\) ak taká neexistuje.

Hodnotenie

Je 8 sád vstupov. Platia v nich nasledujúce obmedzenia:

V prvej sade navyše platí, že vzdialenosti zastávok od domu sú z množiny \(\{1, 2\}\).

Príklad

Input:

5 4
3 4 5 4 5
2 3 4 1
3 4 1 2
1 2 4 1
1 2 4 2

Output:

2
-1
2
-1

Input:

10 5
3 3 1 3 3 2 1 3 3 1
1 5 3 1
1 8 3 1
2 8 3 2
1 4 1 1
1 6 1 2

Output:

1
1
4
3
-1