על מכונה אחת ישנן $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$.