V každej správnej záhradke by mal byť strážny pes. Preto aj my máme na záhradke nášho KSPsa¹, ktorý dáva pozor, aby nenastal žiadny nepríjemný incident. Záhradka je ale veľmi veľká a sám ju neustriehne. Preto má v záhradke aj pomocníkov – malých KSPsíkov! Keďže sú to ale ešte len malé šteniatka, musí na nich dávať dobrý pozor a preto teraz celé dni chodí od jedného k druhému a kontroluje ich.

KSPsíkovia sú, prirodzene, veľmi inteligentní, no trochu nedočkaví. Preto si začali v hlave počítať, pri ktorom z nich zastane KSPs niekedy v budúcnosti. Jednému z nich sa už ale počítať v hlave nechce, a preto by chcel, aby ste mu pomohli.

Úloha

Naša záhradka má tvar jednodimenzionálneho (jednorozmerného) poľa, ktorého políčka sú buď prázdne, alebo je na nich KSPsík. Tí sa nehýbu a po celý čas zostávajú na svojich pôvodných políčkach. KSPs sa na začiatku nachádza na niektorom políčku s KSPsíkom a pozerá sa smerom doprava, potom sa v každom kroku správa nasledovne:

• Ak vidí vo svojom smere nejakého KSPsíka vo vzdialenosti $\le x$, ide za ním.

• Ak nie, tak zistí, že či je opačným smerom nejaký KSPsík vo vzdialenosti $\le x$. Ak je, tak sa otočí a ide za ním.

• Inak ostáva na svojom mieste.

Vašou úlohou je zistiť, na ktorom políčku sa bude KSPs nachádzať po $k$ takýchto krokoch.

Formát vstupu

Na prvom riadku dostanete štyri čísla $n, s, x, k$, kde $n$ je počet KSPsíkov, $s$ označuje KSPsíka, na ktorého políčku KSPs začína, $x$ je vzdialenosť na ktorú KSPs dovidí a $k$ je počet krokov.

Nasleduje jeden riadok, ktorý obsahuje $n$ usporiadaných celých čísel $n_i$, kde $n_i$ označuje pozíciu $i$-tého KSPsíka. KSPs začina na políčku $n_s$.

Dajte si pozor, že niektoré čísla na vstupe sa nemusia zmestiť do obyčajnej 32-bitovej premennej. Odporúčame použiť 64-bitové premenné (long long v C/C++).

Formát výstupu

Vypíšte jediné číslo – číslo políčka, na ktorom sa bude KSPs nachádzať po tom, čo urobí $k$ krokov.

Hodnotenie

Je 8 sád vstupov. Platia v nich nasledovné obmedzenia:

Príklad

Input:

4 2 10 3
1 3 5 7

Output:

3

KSPs začína na políčku s číslom $5$, v ďalšom kroku pôjde doprava k najbližšiemu KSPsíkovi na políčko $7$. Potom sa už ale musí otočiť a vrátiť na políčko $5$, keďže ďalej už nie je žiadny KSPsík. V poslednom kroku prejde na políčko $3$.

Input:

3 1 1 47
0 2 4

Output:

2

KSPs nevidí na žiadneho ďalšieho KSPsíka (keďže sú príliš ďaleko) a preto ostane na pôvodnom mieste.