CSES - Hotelli
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Hotellissa on n huonetta, joista jokaisella on tietty koko. Luoksesi saapuu m asiakasta, jotka haluavat huoneen. Jokaisella asiakkaalla on vaatimus, kuinka suuri huoneen täytyy olla vähintään.

Tehtäväsi on käsitellä asiakkaat järjestyksessä ja antaa kullekin pienin huone, jonka koko on hänen vaatimuksensa mukainen, jos tällainen huone on olemassa. Samaa huonetta ei voi antaa usealle asiakkaalle.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja m: huoneiden määrä ja asiakkaiden määrä.

Seuraavalla rivillä on n kokonaislukua h_1,h_2,\ldots,h_n: huoneiden koot.

Viimeisellä rivillä on m kokonaislukua a_1,a_2,\ldots,a_m: asiakkaiden vaatimukset.

Tuloste

Tulosta m riviä: kunkin asiakkaan huoneen koko. Jos sopivaa huonetta ei ole, tulosta -1.

Rajat

  • 1 \le n,m \le 2 \cdot 10^5
  • 1 \le h_i, a_i \le 10^9

Esimerkki

Syöte:

5 4
2 3 2 5 4
3 3 6 1

Tuloste:

3 4 -1 2

Selitys: Asiakas 1 saa huoneen, jonka koko on 3. Asiakas 2 saa huoneen, jonka koko on 4. Asiakas 3:lle ei löydy huonetta. Asiakas 4 saa huoneen, jonka koko on 2.