Trên một cỗ máy, có $n$ tác vụ độc lập đang chờ được lập lịch. Một tác vụ bắt đầu thực thi tại thời điểm $t$ sẽ hoàn thành tại thời điểm $t+1$. Tất cả các tác vụ chỉ có thể bắt đầu tại các thời điểm nguyên; ngay khi một tác vụ hoàn thành, có thể lập tức bắt đầu một tác vụ khác. Trong quá trình một tác vụ đang được thực thi, không thể thực thi tác vụ nào khác.
Các tác vụ có tính thời hạn. Điều này được biểu diễn như sau: thời điểm bắt đầu của tác vụ thứ $i$ phải nằm trong khoảng từ thời điểm $l_i$ đến thời điểm $r_i$ (tính cả hai đầu mút).
Ngoài ra, còn có $m$ ràng buộc. Ràng buộc thứ $j$ cho biết trong khoảng từ thời điểm $p_j$ đến thời điểm $q_j$ (tính cả hai đầu mút), có tối đa một tác vụ được bắt đầu.
Hãy xác định thời điểm bắt đầu của mỗi tác vụ sao cho thỏa mãn các yêu cầu trên.
Dữ liệu vào
Bài toán này bao gồm nhiều bộ dữ liệu kiểm tra.
Dòng đầu tiên của dữ liệu vào chứa số nguyên không âm $T$, biểu thị số lượng bộ dữ liệu kiểm tra.
Tiếp theo lần lượt là các bộ dữ liệu kiểm tra, đối với mỗi bộ dữ liệu kiểm tra:
Dòng đầu tiên chứa hai số nguyên $n$ và $m$.
$n$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l_i$ và $r_i$, biểu thị khoảng thời gian khả dụng của tác vụ thứ $i$.
$m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $p_j$ và $q_j$, biểu thị khoảng thời gian của ràng buộc lập lịch thứ $j$.
Dữ liệu ra
Đối với mỗi bộ dữ liệu, in ra một dòng gồm $n$ số nguyên, lần lượt biểu thị thời điểm bắt đầu của mỗi tác vụ. Đặc biệt, nếu không tồn tại phương án khả thi, hãy in ra Impossible. Nếu có nhiều phương án khả thi, chỉ cần in ra một phương án bất kỳ.
Ví dụ 1
Dữ liệu vào
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
Dữ liệu ra
7 1 3 9 8 6 Impossible
Ghi chú
Ví dụ này thỏa mãn giới hạn của nhiệm vụ con $1$.
- Đối với bộ dữ liệu thứ nhất, hai tác vụ lần lượt bắt đầu tại thời điểm $7,1$. Cả hai đều nằm trong phạm vi $[l,r]$ tương ứng và thỏa mãn mọi ràng buộc.
- Đối với bộ dữ liệu thứ tư, cả ba tác vụ đầu tiên đều chỉ có thể bắt đầu tại thời điểm $6$ hoặc $7$. Do đó không tồn tại phương án khả thi.
Ví dụ 2
Xem tệp đính kèm ex_data2.in và ex_data2.ans.
Ví dụ này thỏa mãn giới hạn của nhiệm vụ con $2$.
Ví dụ 3
Xem tệp đính kèm ex_data3.in và ex_data3.ans.
Ví dụ này thỏa mãn giới hạn của nhiệm vụ con $3$.
Ví dụ 4
Xem tệp đính kèm ex_data4.in và ex_data4.ans.
Ví dụ này thỏa mãn giới hạn của nhiệm vụ con $4$.
Ví dụ 5
Xem tệp đính kèm ex_data5.in và ex_data5.ans.
Ví dụ này thỏa mãn giới hạn của nhiệm vụ con $5$.
Ví dụ 6
Xem tệp đính kèm ex_data6.in và ex_data6.ans.
Ví dụ này thỏa mãn giới hạn của nhiệm vụ con $6$.
Ví dụ 7
Xem tệp đính kèm ex_data7.in và ex_data7.ans.
Ví dụ này thỏa mãn giới hạn của nhiệm vụ con $7$.
Ví dụ 8
Xem tệp đính kèm ex_data8.in và ex_data8.ans.
Ví dụ này thỏa mãn giới hạn của nhiệm vụ con $8$.
Giới hạn
Gọi $N,M$ lần lượt là tổng của $n,m$ qua tất cả các bộ dữ liệu kiểm tra trong một điểm kiểm tra. Đối với mọi dữ liệu kiểm tra, luôn có:
- $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}$.
| Nhiệm vụ con | $N\le$ | $M\le$ | Tính chất đặc biệt | Điểm |
|---|---|---|---|---|
| $1$ | $10$ | $10$ | Không có | $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$ | Không có | $15$ |
| $8$ | $2.5\times 10^5$ | $2.5\times 10^5$ | Không có | $15$ |
$\rm A$: Đảm bảo $n\le100$, và với mọi $1\le i< n$, đều có $l_i\le l_{i+1}$, $r_i\le r_{i+1}$.
$\rm B$: Với mọi $1\le i\le n$, đều có $r_i\le 5\max(n,m)$.
$\rm C$: Với mọi $1\le i\le m$, đều có $p_i=i,q_i=i+1$, và với mọi $1\le i\le n$, đều có $r_i\le m$.