Su una macchina ci sono $n$ compiti indipendenti in attesa di essere pianificati. Un compito avviato all'istante $t$ termina all'istante $t+1$. Tutti i compiti possono essere avviati solo in istanti interi; non appena un compito termina, è possibile avviarne immediatamente un altro. Mentre un compito è in esecuzione, non è possibile eseguire altri compiti.
I compiti hanno vincoli temporali: l'istante di avvio dell'$i$-esimo compito deve essere compreso tra l'istante $l_i$ e l'istante $r_i$ (estremi inclusi).
Inoltre, ci sono $m$ vincoli. Il $j$-esimo vincolo stabilisce che tra l'istante $p_j$ e l'istante $q_j$ (estremi inclusi) può essere avviato al massimo un compito.
Determina l'istante di avvio di ciascun compito in modo da soddisfare tutti i requisiti sopra indicati.
Input
Questo problema contiene più casi di test.
La prima riga dell'input contiene un intero non negativo $T$, che indica il numero di casi di test.
Seguono nell'ordine i singoli casi di test. Per ciascun caso di test:
La prima riga contiene due interi $n$ e $m$.
Le successive $n$ righe contengono ciascuna due interi $l_i$ e $r_i$, che indicano l'intervallo di tempo disponibile per l'$i$-esimo compito.
Le successive $m$ righe contengono ciascuna due interi $p_j$ e $q_j$, che indicano l'intervallo del $j$-esimo vincolo di pianificazione.
Output
Per ciascun caso di test, stampa una riga contenente $n$ interi, che indicano nell'ordine l'istante di avvio di ciascun compito. In particolare, se non esiste alcuna soluzione valida, stampa Impossible. Se esistono più soluzioni valide, puoi stamparne una qualsiasi.
Esempio 1
Input
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
Output
7 1 3 9 8 6 Impossible
Note
Questo esempio soddisfa i limiti del subtask $1$.
- Nel primo caso di test, i due compiti vengono avviati rispettivamente agli istanti $7,1$. Entrambi rientrano nel rispettivo intervallo $[l,r]$ e soddisfano tutti i vincoli.
- Nel quarto caso di test, i primi tre compiti possono essere avviati solo all'istante $6$ oppure $7$. Pertanto non esiste alcuna soluzione valida.
Esempio 2
Vedi i file ex_data2.in ed ex_data2.ans nei file allegati.
Questo esempio soddisfa i limiti del subtask $2$.
Esempio 3
Vedi i file ex_data3.in ed ex_data3.ans nei file allegati.
Questo esempio soddisfa i limiti del subtask $3$.
Esempio 4
Vedi i file ex_data4.in ed ex_data4.ans nei file allegati.
Questo esempio soddisfa i limiti del subtask $4$.
Esempio 5
Vedi i file ex_data5.in ed ex_data5.ans nei file allegati.
Questo esempio soddisfa i limiti del subtask $5$.
Esempio 6
Vedi i file ex_data6.in ed ex_data6.ans nei file allegati.
Questo esempio soddisfa i limiti del subtask $6$.
Esempio 7
Vedi i file ex_data7.in ed ex_data7.ans nei file allegati.
Questo esempio soddisfa i limiti del subtask $7$.
Esempio 8
Vedi i file ex_data8.in ed ex_data8.ans nei file allegati.
Questo esempio soddisfa i limiti del subtask $8$.
Limiti
Siano $N,M$ rispettivamente le somme di $n,m$ su tutti i casi di test di un singolo testcase. Per tutti i dati di test vale:
- $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}$.
| Subtask | $N\le$ | $M\le$ | Proprietà speciale | Punteggio |
|---|---|---|---|---|
| $1$ | $10$ | $10$ | Nessuna | $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$ | Nessuna | $15$ |
| $8$ | $2.5\times 10^5$ | $2.5\times 10^5$ | Nessuna | $15$ |
$\rm A$: È garantito che $n\le100$, e per ogni $1\le i< n$ vale $l_i\le l_{i+1}$ e $r_i\le r_{i+1}$.
$\rm B$: Per ogni $1\le i\le n$ vale $r_i\le 5\max(n,m)$.
$\rm C$: Per ogni $1\le i\le m$ vale $p_i=i,q_i=i+1$, e per ogni $1\le i\le n$ vale $r_i\le m$.