1 台のマシン上で、依存関係のない $n$ 個のタスクがスケジュールされるのを待っています。時刻 $t$ に実行を開始したタスクは、時刻 $t+1$ に完了します。すべてのタスクは整数の時刻にのみ開始でき、あるタスクが完了した瞬間に直ちに別のタスクを開始することができます。あるタスクの実行中は、他のタスクを実行することはできません。
各タスクには実行可能な時間帯が定められています。具体的には、$i$ 番目のタスクの開始時刻は時刻 $l_i$ から時刻 $r_i$ の間（両端を含む）でなければなりません。
さらに、$m$ 個の制約があります。$j$ 番目の制約は、時刻 $p_j$ から時刻 $q_j$ の間（両端を含む）に開始できるタスクは高々 1 個であることを表します。
上記の条件をすべて満たすように、各タスクの開始時刻を決定してください。
入力
この問題には複数のテストケースが含まれます。
入力の 1 行目には、テストケースの個数を表す非負整数 $T$ が与えられます。
続いて各テストケースが順番に与えられます。各テストケースの形式は以下の通りです：
1 行目には 2 つの整数 $n$ と $m$ が与えられます。
続く $n$ 行には、それぞれ 2 つの整数 $l_i$ と $r_i$ が与えられ、$i$ 番目のタスクの利用可能な時間区間を表します。
続く $m$ 行には、それぞれ 2 つの整数 $p_j$ と $q_j$ が与えられ、$j$ 番目のスケジューリング制約区間を表します。
出力
各テストケースについて、各タスクの開始時刻を順番に表す $n$ 個の整数を 1 行に出力してください。特に、条件を満たすスケジュールが存在しない場合は、Impossible と出力してください。条件を満たすスケジュールが複数存在する場合は、どれを出力しても構いません。
入出力例 1
入力
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
出力
7 1 3 9 8 6 Impossible
注記
この入出力例は小課題 $1$ の制約を満たします。
- 1 つ目のテストケースでは、2 つのタスクはそれぞれ時刻 $7,1$ に開始されます。どちらもそれぞれの $[l,r]$ の範囲内にあり、すべての制約を満たしています。
- 4 つ目のテストケースでは、最初の 3 つのタスクはいずれも時刻 $6$ または $7$ にしか開始できません。したがって、条件を満たすスケジュールは存在しません。
入出力例 2
配布ファイル内の ex_data2.in および ex_data2.ans を参照してください。
この入出力例は小課題 $2$ の制約を満たします。
入出力例 3
配布ファイル内の ex_data3.in および ex_data3.ans を参照してください。
この入出力例は小課題 $3$ の制約を満たします。
入出力例 4
配布ファイル内の ex_data4.in および ex_data4.ans を参照してください。
この入出力例は小課題 $4$ の制約を満たします。
入出力例 5
配布ファイル内の ex_data5.in および ex_data5.ans を参照してください。
この入出力例は小課題 $5$ の制約を満たします。
入出力例 6
配布ファイル内の ex_data6.in および ex_data6.ans を参照してください。
この入出力例は小課題 $6$ の制約を満たします。
入出力例 7
配布ファイル内の ex_data7.in および ex_data7.ans を参照してください。
この入出力例は小課題 $7$ の制約を満たします。
入出力例 8
配布ファイル内の ex_data8.in および ex_data8.ans を参照してください。
この入出力例は小課題 $8$ の制約を満たします。
制約
$N,M$ をそれぞれ 1 つのテストケースファイル内のすべてのテストケースにおける $n,m$ の総和とします。すべてのテストデータにおいて、以下が成り立ちます：
- $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}$
| 小課題番号 | $N\le$ | $M\le$ | 追加制約 | 配点 |
|---|---|---|---|---|
| $1$ | $10$ | $10$ | なし | $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$ | なし | $15$ |
| $8$ | $2.5\times 10^5$ | $2.5\times 10^5$ | なし | $15$ |
$\rm A$：$n\le100$ が保証され、すべての $1\le i< n$ について $l_i\le l_{i+1}$ かつ $r_i\le r_{i+1}$ が成り立つ。
$\rm B$：すべての $1\le i\le n$ について $r_i\le 5\max(n,m)$ が成り立つ。
$\rm C$：すべての $1\le i\le m$ について $p_i=i,q_i=i+1$ が成り立ち、かつすべての $1\le i\le n$ について $r_i\le m$ が成り立つ。