Alice og Bob ætla að spila spilaleik. Það eru $n$ spil og á hvert þeirra er skrifuð heiltala. Leikurinn fer fram á eftirfarandi hátt:
- Alice velur heiltölu á milli $a$ og $b$, báðum meðtöldum. Köllum þessa heiltölu $t$. Alice segir síðan Bob gildið á $t$.
- Bob velur $k$ af þessum $n$ spilum. Reiknuð er summa heiltalnanna sem skrifaðar eru á spilin $k$ sem Bob velur. Köllum þessa summu $u$.
Markmið Alice er að gera $|t - u|$ eins stórt og mögulegt er og markmið Bobs er að gera $|t - u|$ eins lítið og mögulegt er. Áður en leikurinn hefst vita bæði Alice og Bob gildin á $n$, $k$, $a$ og $b$, sem og heiltölurnar á spilunum. Bæði Alice og Bob munu spila á besta mögulega hátt. Sér í lagi mun Alice taka ákvörðun sína vitandi að Bob mun örugglega lágmarka $|t - u|$ fyrir uppgefið $t$. Gerum að auki ráð fyrir að Alice kjósi frekar að velja minna $t$ ef hún hefur marga jafngóða valkosti.
Verkefni þitt er að ákvarða niðurstöðu leiksins: gildið á $t$ sem Alice mun velja og spilin $k$ sem Bob mun velja fyrir það $t$.
Inntak
Inntakið samanstendur af tveimur línum sem tákna eitt prófunartilvik. Fyrri línan inniheldur fjórar heiltölur $n$, $k$, $a$ og $b$ ($1 \le k \le n \le 600$, $0 \le a \le b \le 1.8 \cdot 10^5$). Seinni línan inniheldur $n$ heiltölur $x_1, \ldots, x_n$ ($0 \le x_i \le 300$), sem tákna að $x_i$ sé skrifað á $i$-ta spilið.
Úttak
Skrifið út tvær línur: Fyrri línan á að innihalda heiltölu sem táknar gildið á $t$ sem Alice mun velja. Seinni línan á að innihalda $k$ ólíkar heiltölur á milli $1$ og $n$, báðum meðtöldum, sem tákna númer spilanna sem Bob mun velja. Ef Bob hefur marga jafngóða valkosti má skrifa út hvern sem er þeirra.
Dæmi
Inntak 1
4 2 58 100 10 10 50 80
Úttak 1
75 2 3
Inntak 2
8 3 1300 1800 2 0 1 5 0 4 1 9
Úttak 2
1800 4 6 8