题目描述

一台机器上，有 $n$ 个无依赖关系的任务等待被调度。在 $t$ 时刻启动执行的任务，会在 $t+1$ 时刻完成。所有任务只能在整数时刻启动；一个任务完成时，可以立即启动另一个任务。在一个任务执行的过程中，无法执行别的任务。

任务具有时效性。可以被表示为：第 $i$ 个任务的启动时刻，必须在 $l_i$ 时刻到 $r_i$ 时刻（包含两边）之间。

此外，还有 $m$ 条约束。第 $j$ 个约束表示，在 $p_j$ 时刻到 $q_j$ 时刻（包含两边）之间，最多只能启动一个任务。

请确定每个任务的启动时刻，满足上述要求。

输入格式

本题包含多组测试数据。

输入的第一行包含非负整数 $T$，表示测试数据组数。

接下来依次输入每组测试数据，对于每组测试数据：

• 第一行包含两个整数 $n$ 和 $m$。

• 接下来 $n$ 行，每行两个整数 $l_i$ 和 $r_i$，表示第 $i$ 个任务的可用时间区间。

• 接下来 $m$ 行，每行两个整数 $p_j$ 和 $q_j$，表示第 $j$ 个调度约束区间。

输出格式

对于每组数据，输出一行 $n$ 个整数，依次表示每个任务的启动时刻。特别地，若不存在可行方案，则输出 Impossible。若存在多组可行方案，输出任意一组即可。

样例一

输入

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$ 的限制。

• 对于第一组数据，两个任务分别在时刻 $7,1$ 启动。均在各自的 $[l,r]$ 范围内，且满足所有约束。
• 对于第四组数据，前三个任务都只能在时刻 $6$ 或 $7$ 启动。故不存在可行的方案。

样例二

见下发文件中的 ex_data2.in 和 ex_data2.ans。

本样例满足子任务 $2$ 的限制。

样例三

见下发文件中的 ex_data3.in 和 ex_data3.ans。

本样例满足子任务 $3$ 的限制。

样例四

见下发文件中的 ex_data4.in 和 ex_data4.ans。

本样例满足子任务 $4$ 的限制。

样例五

见下发文件中的 ex_data5.in 和 ex_data5.ans。

本样例满足子任务 $5$ 的限制。

样例六

见下发文件中的 ex_data6.in 和 ex_data6.ans。

本样例满足子任务 $6$ 的限制。

样例七

见下发文件中的 ex_data7.in 和 ex_data7.ans。

本样例满足子任务 $7$ 的限制。

样例八

见下发文件中的 ex_data8.in 和 ex_data8.ans。

本样例满足子任务 $8$ 的限制。

数据范围

设 $N,M$ 分别为单个测试点内所有测试数据的 $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}$。

$\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$。