På én maskin venter $n$ uavhengige oppgaver på å bli planlagt. En oppgave som starter ved tidspunkt $t$, blir ferdig ved tidspunkt $t+1$. Alle oppgaver kan kun startes ved heltallige tidspunkter; så snart en oppgave er ferdig, kan en annen oppgave startes umiddelbart. Mens en oppgave kjører, kan ingen andre oppgaver kjøres.

Oppgavene er tidsfølsomme. Dette kan uttrykkes ved at starttidspunktet for den $i$-te oppgaven må være mellom tidspunkt $l_i$ og tidspunkt $r_i$ (inkludert begge ytterpunktene).

I tillegg finnes det $m$ restriksjoner. Den $j$-te restriksjonen sier at mellom tidspunkt $p_j$ og tidspunkt $q_j$ (inkludert begge ytterpunktene) kan høyst én oppgave startes.

Bestem starttidspunktet for hver oppgave slik at alle kravene ovenfor er oppfylt.

Inndata

Denne oppgaven inneholder flere testtilfeller.

Den første linjen i inndataene inneholder et ikke-negativt heltall $T$, som angir antall testtilfeller.

Deretter følger hvert testtilfelle i rekkefølge. For hvert testtilfelle:

• Den første linjen inneholder to heltall $n$ og $m$.

• De neste $n$ linjene inneholder hver to heltall $l_i$ og $r_i$, som angir det tilgjengelige tidsintervallet for den $i$-te oppgaven.

• De neste $m$ linjene inneholder hver to heltall $p_j$ og $q_j$, som angir intervallet for den $j$-te planleggingsrestriksjonen.

Utdata

For hvert testtilfelle skal du skrive ut én linje med $n$ heltall som i rekkefølge angir starttidspunktet for hver oppgave. Spesielt, dersom det ikke finnes noen gyldig løsning, skriv ut Impossible. Dersom det finnes flere gyldige løsninger, kan du skrive ut hvilken som helst av dem.

Eksempel 1

Inndata

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

Forklaring

Dette eksempelet oppfyller begrensningene i deloppgave $1$.

• For det første testtilfellet starter de to oppgavene ved henholdsvis tidspunkt $7,1$. Begge er innenfor sine respektive $[l,r]$-intervaller og oppfyller alle restriksjoner.
• For det fjerde testtilfellet kan de tre første oppgavene kun starte ved tidspunkt $6$ eller $7$. Derfor finnes det ingen gyldig løsning.

Eksempel 2

Se ex_data2.in og ex_data2.ans i de vedlagte filene.

Dette eksempelet oppfyller begrensningene i deloppgave $2$.

Eksempel 3

Se ex_data3.in og ex_data3.ans i de vedlagte filene.

Dette eksempelet oppfyller begrensningene i deloppgave $3$.

Eksempel 4

Se ex_data4.in og ex_data4.ans i de vedlagte filene.

Dette eksempelet oppfyller begrensningene i deloppgave $4$.

Eksempel 5

Se ex_data5.in og ex_data5.ans i de vedlagte filene.

Dette eksempelet oppfyller begrensningene i deloppgave $5$.

Eksempel 6

Se ex_data6.in og ex_data6.ans i de vedlagte filene.

Dette eksempelet oppfyller begrensningene i deloppgave $6$.

Eksempel 7

Se ex_data7.in og ex_data7.ans i de vedlagte filene.

Dette eksempelet oppfyller begrensningene i deloppgave $7$.

Eksempel 8

Se ex_data8.in og ex_data8.ans i de vedlagte filene.

Dette eksempelet oppfyller begrensningene i deloppgave $8$.

Begrensninger

La $N,M$ være summen av henholdsvis $n,m$ over alle testtilfeller i ett enkelt testpunkt. For alle testdata gjelder:

• $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}$.

$\rm A$: Det garanteres at $n\le100$, og for alle $1\le i< n$ gjelder $l_i\le l_{i+1}$ og $r_i\le r_{i+1}$.

$\rm B$: For alle $1\le i\le n$ gjelder $r_i\le 5\max(n,m)$.

$\rm C$: For alle $1\le i\le m$ gjelder $p_i=i,q_i=i+1$, og for alle $1\le i\le n$ gjelder $r_i\le m$.