한 기계에서 의존 관계가 없는 $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을 출력합니다. 가능한 방법이 여러 가지인 경우 그중 아무것이나 하나를 출력하면 됩니다.
예제 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$의 조건을 만족합니다.
- 첫 번째 테스트 케이스에서 두 작업은 각각 시각 $7,1$에 시작합니다. 모두 각자의 $[l,r]$ 범위 내에 있으며 모든 제약 조건을 만족합니다.
- 네 번째 테스트 케이스에서 처음 세 작업은 모두 시각 $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$을 각각 단일 테스트 데이터 내 모든 테스트 케이스의 $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$입니다.