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

Hotellissa on nn huonetta, joista jokaisella on tietty koko. Luoksesi saapuu mm 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 nn ja mm: huoneiden määrä ja asiakkaiden määrä.

Seuraavalla rivillä on nn kokonaislukua h1,h2,,hnh_1,h_2,\ldots,h_n: huoneiden koot.

Viimeisellä rivillä on mm kokonaislukua a1,a2,,ama_1,a_2,\ldots,a_m: asiakkaiden vaatimukset.

Tuloste

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

Rajat

  • 1n,m21051 \le n,m \le 2 \cdot 10^5
  • 1hi,ai1091 \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.