2. Aha, psíky!

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.