На одній машині є $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$.