På en maskin finns det $n$ oberoende uppgifter som väntar på att schemaläggas. En uppgift som börjar köras vid tidpunkt $t$ blir klar vid tidpunkt $t+1$. Alla uppgifter kan endast startas vid heltalstidpunkter; så snart en uppgift är klar kan en annan uppgift startas omedelbart. Medan en uppgift körs kan ingen annan uppgift köras.
Uppgifterna är tidsbegränsade. Detta kan uttryckas som att starttidpunkten för den $i$-te uppgiften måste ligga mellan tidpunkt $l_i$ och tidpunkt $r_i$ (inklusive ändpunkterna).
Dessutom finns det $m$ villkor. Det $j$-te villkoret anger att mellan tidpunkt $p_j$ och tidpunkt $q_j$ (inklusive ändpunkterna) får högst en uppgift startas.
Bestäm starttidpunkten för varje uppgift så att alla ovanstående krav uppfylls.
Indata
Detta problem innehåller flera testfall.
Den första raden i indata innehåller ett icke-negativt heltal $T$, som anger antalet testfall.
Därefter följer testfallen i ordning. För varje testfall gäller:
Den första raden innehåller två heltal $n$ och $m$.
De följande $n$ raderna innehåller vardera två heltal $l_i$ och $r_i$, som anger det tillgängliga tidsintervallet för den $i$-te uppgiften.
De följande $m$ raderna innehåller vardera två heltal $p_j$ och $q_j$, som anger intervallet för det $j$-te schemaläggningsvillkoret.
Utdata
För varje testfall, skriv ut en rad med $n$ heltal som i ordning anger starttidpunkten för varje uppgift. Särskilt gäller att om ingen giltig lösning existerar, skriv ut Impossible. Om det finns flera giltiga lösningar kan du skriva ut vilken som helst av dem.
Exempel 1
Indata
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
Utdata
7 1 3 9 8 6 Impossible
Förklaring
Detta exempel uppfyller begränsningarna för deluppgift $1$.
- För det första testfallet startar de två uppgifterna vid tidpunkterna $7,1$. Båda ligger inom sina respektive intervall $[l,r]$ och uppfyller alla villkor.
- För det fjärde testfallet kan de tre första uppgifterna endast starta vid tidpunkt $6$ eller $7$. Därför finns det ingen giltig lösning.
Exempel 2
Se ex_data2.in och ex_data2.ans i de bifogade filerna.
Detta exempel uppfyller begränsningarna för deluppgift $2$.
Exempel 3
Se ex_data3.in och ex_data3.ans i de bifogade filerna.
Detta exempel uppfyller begränsningarna för deluppgift $3$.
Exempel 4
Se ex_data4.in och ex_data4.ans i de bifogade filerna.
Detta exempel uppfyller begränsningarna för deluppgift $4$.
Exempel 5
Se ex_data5.in och ex_data5.ans i de bifogade filerna.
Detta exempel uppfyller begränsningarna för deluppgift $5$.
Exempel 6
Se ex_data6.in och ex_data6.ans i de bifogade filerna.
Detta exempel uppfyller begränsningarna för deluppgift $6$.
Exempel 7
Se ex_data7.in och ex_data7.ans i de bifogade filerna.
Detta exempel uppfyller begränsningarna för deluppgift $7$.
Exempel 8
Se ex_data8.in och ex_data8.ans i de bifogade filerna.
Detta exempel uppfyller begränsningarna för deluppgift $8$.
Begränsningar
Låt $N,M$ vara summan av $n,m$ över alla testfall i en enskild testpunkt. För alla testdata gäller:
- $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}$.
| Deluppgift | $N\le$ | $M\le$ | Särskild egenskap | Poäng |
|---|---|---|---|---|
| $1$ | $10$ | $10$ | Ingen | $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$ | Ingen | $15$ |
| $8$ | $2.5\times 10^5$ | $2.5\times 10^5$ | Ingen | $15$ |
$\rm A$: Det garanteras att $n\le100$, och för alla $1\le i< n$ gäller $l_i\le l_{i+1}$ samt $r_i\le r_{i+1}$.
$\rm B$: För alla $1\le i\le n$ gäller $r_i\le 5\max(n,m)$.
$\rm C$: För alla $1\le i\le m$ gäller $p_i=i,q_i=i+1$, och för alla $1\le i\le n$ gäller $r_i\le m$.