Бір машинада бір-біріне тәуелсіз $n$ тапсырма жоспарлануды күтіп тұр. $t$ уақыт мезетінде орындалуы басталған тапсырма $t+1$ уақыт мезетінде аяқталады. Барлық тапсырмалар тек бүтін уақыт мезеттерінде ғана бастала алады; бір тапсырма аяқталған кезде бірден келесі тапсырманы бастауға болады. Бір тапсырма орындалып жатқан кезде басқа ешбір тапсырма орындала алмайды.
Тапсырмалардың уақыттық шектеулері бар: $i$-ші тапсырманың басталу уақыты $l_i$ мезеті мен $r_i$ мезетінің аралығында (екі шетін қоса алғанда) болуы тиіс.
Сонымен қатар $m$ шектеу бар. $j$-ші шектеу $p_j$ мезеті мен $q_j$ мезетінің аралығында (екі шетін қоса алғанда) ең көп дегенде бір ғана тапсырма бастала алатынын білдіреді.
Жоғарыдағы талаптардың барлығы орындалатындай етіп әр тапсырманың басталу уақытын анықтаңыз.
Кіріс деректер
Бұл есеп бірнеше тест деректері жиынынан тұрады.
Кіріс деректердің бірінші жолында тест деректері жиынының санын білдіретін теріс емес бүтін $T$ саны берілген.
Одан кейін әрбір тест деректері жиыны ретімен беріледі. Әрбір тест деректері жиыны үшін:
Бірінші жолда екі бүтін $n$ және $m$ сандары берілген.
Келесі $n$ жолдың әрқайсысында $i$-ші тапсырманың қолжетімді уақыт аралығын білдіретін екі бүтін $l_i$ және $r_i$ сандары берілген.
Келесі $m$ жолдың әрқайсысында $j$-ші жоспарлау шектеуінің аралығын білдіретін екі бүтін $p_j$ және $q_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$ орындалады.