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:
Sada | 1–2 | 3 | 4 | 5–8 |
---|---|---|---|---|
\(1 \leq n \leq\) | \(100\) | \(10\,000\) | \(80\,000\) | \(100\,000\) |
\(1 \leq q \leq\) | \(100\) | \(10\,000\) | \(100\,000\) | \(100\,000\) |
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
Odovzdávanie
Na odovzdávanie sa musíš prihlásiť
Otázky a diskusia
Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.