Yhdellä koneella on $n$ toisistaan riippumatonta tehtävää odottamassa aikataulutusta. Ajanhetkellä $t$ käynnistetty tehtävä valmistuu ajanhetkellä $t+1$. Kaikki tehtävät voidaan käynnistää vain kokonaislukuaikoina; heti kun yksi tehtävä valmistuu, voidaan välittömästi käynnistää toinen tehtävä. Kun yhtä tehtävää suoritetaan, mitään muuta tehtävää ei voida suorittaa.
Tehtävillä on aikarajat. Tämä voidaan ilmaista niin, että $i$:nnen tehtävän käynnistysajan on oltava ajanhetkien $l_i$ ja $r_i$ välissä (mukaan lukien päätepisteet).
Lisäksi on $m$ rajoitusta. $j$:s rajoitus ilmaisee, että ajanhetkien $p_j$ ja $q_j$ välissä (mukaan lukien päätepisteet) voidaan käynnistää enintään yksi tehtävä.
Määritä jokaiselle tehtävälle käynnistysaika siten, että kaikki yllä mainitut vaatimukset täyttyvät.
Syöte
Tämä tehtävä sisältää useita testitapauksia.
Syötteen ensimmäisellä rivillä on ei-negatiivinen kokonaisluku $T$, joka ilmoittaa testitapausten lukumäärän.
Seuraavaksi annetaan kukin testitapaus järjestyksessä. Jokaiselle testitapaukselle:
Ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $m$.
Seuraavilla $n$ rivillä on kullakin kaksi kokonaislukua $l_i$ ja $r_i$, jotka ilmoittavat $i$:nnen tehtävän sallitun aikavälin.
Seuraavilla $m$ rivillä on kullakin kaksi kokonaislukua $p_j$ ja $q_j$, jotka ilmoittavat $j$:nnen aikataulutusrajoituksen aikavälin.
Tuloste
Tulosta jokaista testitapausta kohden yhdelle riville $n$ kokonaislukua, jotka ilmoittavat järjestyksessä kunkin tehtävän käynnistysajan. Erityisesti, jos kelvollista ratkaisua ei ole olemassa, tulosta Impossible. Jos kelvollisia ratkaisuja on useita, voit tulostaa minkä tahansa niistä.
Esimerkki 1
Syöte
4 2 3 2 7 1 10 7 8 2 10 1 6 2 2 2 5 1 9 1 5 4 9 2 4 3 8 3 6 2 7 4 7 8 9 1 6 4 1 6 7 6 7 6 7 1 11 21 31
Tuloste
7 1 3 9 8 6 Impossible
Huomautus
Tämä esimerkki täyttää osatehtävän $1$ rajoitukset.
- Ensimmäisessä testitapauksessa kaksi tehtävää käynnistetään ajanhetkillä $7,1$. Molemmat ovat omissa $[l,r]$-väleissään ja kaikki rajoitukset täyttyvät.
- Neljännessä testitapauksessa kolme ensimmäistä tehtävää voidaan käynnistää vain ajanhetkellä $6$ tai $7$. Näin ollen kelvollista ratkaisua ei ole olemassa.
Esimerkki 2
Katso oheistiedostoista ex_data2.in ja ex_data2.ans.
Tämä esimerkki täyttää osatehtävän $2$ rajoitukset.
Esimerkki 3
Katso oheistiedostoista ex_data3.in ja ex_data3.ans.
Tämä esimerkki täyttää osatehtävän $3$ rajoitukset.
Esimerkki 4
Katso oheistiedostoista ex_data4.in ja ex_data4.ans.
Tämä esimerkki täyttää osatehtävän $4$ rajoitukset.
Esimerkki 5
Katso oheistiedostoista ex_data5.in ja ex_data5.ans.
Tämä esimerkki täyttää osatehtävän $5$ rajoitukset.
Esimerkki 6
Katso oheistiedostoista ex_data6.in ja ex_data6.ans.
Tämä esimerkki täyttää osatehtävän $6$ rajoitukset.
Esimerkki 7
Katso oheistiedostoista ex_data7.in ja ex_data7.ans.
Tämä esimerkki täyttää osatehtävän $7$ rajoitukset.
Esimerkki 8
Katso oheistiedostoista ex_data8.in ja ex_data8.ans.
Tämä esimerkki täyttää osatehtävän $8$ rajoitukset.
Rajoitukset
Olkoot $N,M$ lukujen $n,m$ summat yksittäisen testipisteen kaikkien testitapausten yli. Kaikilletestisyötteille pätee:
- $1 \le n \le 2.5 \times 10^5,0 \le m \le 2.5 \times 10^5$;
- $1 \le l_i \le r_i \le 10^{9}$;
- $1 \le p_j \le q_j \le 10^{9}$.
| Osatehtävä | $N\le$ | $M\le$ | Erikoisominaisuus | Pisteet |
|---|---|---|---|---|
| $1$ | $10$ | $10$ | Ei ole | $5$ |
| $2$ | $2.5\times 10^5$ | $2.5\times 10^5$ | $\rm A$ | $5$ |
| $3$ | $10^3$ | $10^3$ | $\rm B$ | $15$ |
| $4$ | $2.5\times 10^5$ | $2.5\times 10^5$ | $\rm C$ | $15$ |
| $5$ | $10^4$ | $10^4$ | $\rm B$ | $15$ |
| $6$ | $10^5$ | $10^5$ | $\rm B$ | $15$ |
| $7$ | $10^5$ | $10^5$ | Ei ole | $15$ |
| $8$ | $2.5\times 10^5$ | $2.5\times 10^5$ | Ei ole | $15$ |
$\rm A$: Taataan, että $n\le100$, ja kaikilla $1\le i< n$ pätee $l_i\le l_{i+1}$ sekä $r_i\le r_{i+1}$.
$\rm B$: Kaikilla $1\le i\le n$ pätee $r_i\le 5\max(n,m)$.
$\rm C$: Kaikilla $1\le i\le m$ pätee $p_i=i,q_i=i+1$, ja kaikilla $1\le i\le n$ pätee $r_i\le m$.