Á einni vél bíða $n$ óháð verkefni eftir því að verða röðuð niður. Verkefni sem byrjað er að keyra á tímapunkti $t$ lýkur á tímapunkti $t+1$. Öll verkefni geta aðeins hafist á heiltölutímapunktum; um leið og einu verkefni lýkur er hægt að hefja annað verkefni tafarlaust. Á meðan eitt verkefni er í keyrslu er ekki hægt að keyra neitt annað verkefni.

Verkefnin eru tímabundin. Þetta má setja fram þannig að upphafstími $i$-ta verkefnisins verður að vera á milli tímapunkts $l_i$ og tímapunkts $r_i$ (báðir endapunktar meðtaldir).

Auk þess eru $m$ skorður. $j$-ta skorðan segir að á milli tímapunkts $p_j$ og tímapunkts $q_j$ (báðir endapunktar meðtaldir) megi í mesta lagi hefja eitt verkefni.

Ákvarðið upphafstíma hvers verkefnis þannig að öllum ofangreindum kröfum sé fullnægt.

Inntak

Þetta dæmi inniheldur mörg prófunartilvik.

Fyrsta lína inntaksins inniheldur óneikvæða heiltölu $T$, sem táknar fjölda prófunartilvika.

Því næst koma prófunartilvikin hvert á eftir öðru. Fyrir hvert prófunartilvik:

• Fyrsta línan inniheldur tvær heiltölur $n$ og $m$.

• Næstu $n$ línur innihalda hver um sig tvær heiltölur $l_i$ og $r_i$, sem tákna leyfilegt tímabil fyrir $i$-ta verkefnið.

• Næstu $m$ línur innihalda hver um sig tvær heiltölur $p_j$ og $q_j$, sem tákna tímabil $j$-tu röðunarskorðunnar.

Úttak

Fyrir hvert prófunartilvik skal prenta eina línu með $n$ heiltölum sem tákna í röð upphafstíma hvers verkefnis. Sér í lagi, ef engin gild lausn er til, skal prenta Impossible. Ef margar gildar lausnir eru til má prenta hverja sem er þeirra.

Dæmi 1

Inntak

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

Úttak

7 1
3 9
8 6
Impossible

Skýring

Þetta dæmi uppfyllir skorður undirverkefnis $1$.

• Í fyrsta prófunartilvikinu hefjast verkefnin tvö á tímapunktum $7,1$ í þessari röð. Bæði eru innan síns $[l,r]$ bils og uppfylla allar skorður.
• Í fjórða prófunartilvikinu geta fyrstu þrjú verkefnin aðeins hafist á tímapunkti $6$ eða $7$. Því er engin gild lausn til.

Dæmi 2

Sjá ex_data2.in og ex_data2.ans í meðfylgjandi skrám.

Þetta dæmi uppfyllir skorður undirverkefnis $2$.

Dæmi 3

Sjá ex_data3.in og ex_data3.ans í meðfylgjandi skrám.

Þetta dæmi uppfyllir skorður undirverkefnis $3$.

Dæmi 4

Sjá ex_data4.in og ex_data4.ans í meðfylgjandi skrám.

Þetta dæmi uppfyllir skorður undirverkefnis $4$.

Dæmi 5

Sjá ex_data5.in og ex_data5.ans í meðfylgjandi skrám.

Þetta dæmi uppfyllir skorður undirverkefnis $5$.

Dæmi 6

Sjá ex_data6.in og ex_data6.ans í meðfylgjandi skrám.

Þetta dæmi uppfyllir skorður undirverkefnis $6$.

Dæmi 7

Sjá ex_data7.in og ex_data7.ans í meðfylgjandi skrám.

Þetta dæmi uppfyllir skorður undirverkefnis $7$.

Dæmi 8

Sjá ex_data8.in og ex_data8.ans í meðfylgjandi skrám.

Þetta dæmi uppfyllir skorður undirverkefnis $8$.

Takmarkanir

Látum $N,M$ vera summur $n,m$ í sömu röð yfir öll prófunartilvik í einum prófunarpunkti. Fyrir öll prófunargögn gildir:

• $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$: Tryggt er að $n\le100$, og fyrir öll $1\le i< n$ gildir $l_i\le l_{i+1}$ og $r_i\le r_{i+1}$.

$\rm B$: Fyrir öll $1\le i\le n$ gildir $r_i\le 5\max(n,m)$.

$\rm C$: Fyrir öll $1\le i\le m$ gildir $p_i=i,q_i=i+1$, og fyrir öll $1\le i\le n$ gildir $r_i\le m$.