Code Submission Evaluation System Login

Datatähti-valmennus

Konsertti


Task | Statistics


CSES - Konsertti

Time limit:1.00 s Memory limit:128 MB

Konserttiin on myynnissä $n$ lippua, joilla on tietyt hinnat. Kassalle saapuu $m$ asiakasta, jotka ilmoittavat vuorollaan, paljonko he ovat valmiita maksamaan lipusta. Kunkin asiakkaan tulee saada lippu, jonka hinta on mahdollisimman lähellä hänen ilmoittamaansa hintaa, mutta ei sitä suurempi.

Tehtäväsi on antaa jokaiselle asiakkaalle lippu siinä järjestyksessä kuin asiakkaat tulevat kassalle.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluvut $n$ ja $m$: lippujen määrä ja asiakkaiden määrä.

Seuraavalla rivillä on $n$ kokonaislukua $h_1,h_2,\ldots,h_n$: kunkin lipun hinta.

Viimeisellä rivillä on $m$ kokonaislukua $t_1,t_2,\ldots,t_m$: kunkin asiakkaan tarjous.

Tuloste

Ohjelmasi tulee tulostaa jokaisesta tarjouksesta hinta, jonka asiakas maksaa lipusta. Tämän jälkeen samaa lippua ei voi ostaa uudestaan.

Jos asiakas ei saa mitään lippua, ohjelmasi tulee tulostaa QAQ.

Rajat
Esimerkki

Syöte:
5 3
5 3 7 8 5
4 8 3


Tuloste:
3
8
QAQ