Sur une machine, $n$ tâches indépendantes attendent d'être ordonnancées. Une tâche dont l'exécution commence à l'instant $t$ se termine à l'instant $t+1$. Toutes les tâches ne peuvent commencer qu'à des instants entiers ; dès qu'une tâche se termine, une autre peut commencer immédiatement. Pendant l'exécution d'une tâche, aucune autre tâche ne peut être exécutée.

Les tâches sont soumises à des contraintes de disponibilité : l'instant de début de la $i$-ème tâche doit être compris entre l'instant $l_i$ et l'instant $r_i$ (bornes incluses).

De plus, il y a $m$ contraintes. La $j$-ème contrainte indique qu'entre l'instant $p_j$ et l'instant $q_j$ (bornes incluses), au plus une tâche peut commencer.

Veuillez déterminer l'instant de début de chaque tâche de manière à satisfaire toutes les exigences ci-dessus.

Entrée

Ce problème contient plusieurs cas de test.

La première ligne de l'entrée contient un entier non négatif $T$, représentant le nombre de cas de test.

Les cas de test suivent dans l'ordre. Pour chaque cas de test :

• La première ligne contient deux entiers $n$ et $m$.

• Les $n$ lignes suivantes contiennent chacune deux entiers $l_i$ et $r_i$, représentant l'intervalle de temps disponible pour la $i$-ème tâche.

• Les $m$ lignes suivantes contiennent chacune deux entiers $p_j$ et $q_j$, représentant l'intervalle de la $j$-ème contrainte d'ordonnancement.

Sortie

Pour chaque cas de test, affichez une ligne contenant $n$ entiers, représentant dans l'ordre l'instant de début de chaque tâche. En particulier, s'il n'existe aucune solution valide, affichez Impossible. S'il existe plusieurs solutions valides, vous pouvez afficher n'importe laquelle.

Exemple 1

Entrée

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

Sortie

7 1
3 9
8 6
Impossible

Note

Cet exemple satisfait les contraintes de la sous-tâche $1$.

• Pour le premier cas de test, les deux tâches commencent respectivement aux instants $7,1$. Toutes deux sont dans leur intervalle $[l,r]$ respectif et toutes les contraintes sont satisfaites.
• Pour le quatrième cas de test, les trois premières tâches ne peuvent commencer qu'à l'instant $6$ ou $7$. Il n'existe donc aucune solution valide.

Exemple 2

Voir les fichiers ex_data2.in et ex_data2.ans dans les fichiers fournis.

Cet exemple satisfait les contraintes de la sous-tâche $2$.

Exemple 3

Voir les fichiers ex_data3.in et ex_data3.ans dans les fichiers fournis.

Cet exemple satisfait les contraintes de la sous-tâche $3$.

Exemple 4

Voir les fichiers ex_data4.in et ex_data4.ans dans les fichiers fournis.

Cet exemple satisfait les contraintes de la sous-tâche $4$.

Exemple 5

Voir les fichiers ex_data5.in et ex_data5.ans dans les fichiers fournis.

Cet exemple satisfait les contraintes de la sous-tâche $5$.

Exemple 6

Voir les fichiers ex_data6.in et ex_data6.ans dans les fichiers fournis.

Cet exemple satisfait les contraintes de la sous-tâche $6$.

Exemple 7

Voir les fichiers ex_data7.in et ex_data7.ans dans les fichiers fournis.

Cet exemple satisfait les contraintes de la sous-tâche $7$.

Exemple 8

Voir les fichiers ex_data8.in et ex_data8.ans dans les fichiers fournis.

Cet exemple satisfait les contraintes de la sous-tâche $8$.

Contraintes

Soient $N,M$ les sommes respectives de $n,m$ sur tous les cas de test d'un même fichier de test. Pour tous les cas de test, on a :

• $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$ : Il est garanti que $n\le100$, et pour tout $1\le i< n$, on a $l_i\le l_{i+1}$ et $r_i\le r_{i+1}$.

$\rm B$ : Pour tout $1\le i\le n$, on a $r_i\le 5\max(n,m)$.

$\rm C$ : Pour tout $1\le i\le m$, on a $p_i=i,q_i=i+1$, et pour tout $1\le i\le n$, on a $r_i\le m$.