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