על השולחן יש $n$ חפיסות קלפים. החפיסה ה-$i$ מכילה $a_i$ קלפים, והקלף ה-$j$ מלמעלה למטה הוא $s_{i,j}$. כדי לפשט את הבעיה, נבחין רק בין קלפים גבוהים לנמוכים. אם הקלף גבוה, אז $s_{i,j}=1$. אם הוא נמוך, אז $s_{i,j}=0$.
מסביב לשולחן יושבים $m$ מהמרים ומחכים למשחק קלפים. אתם מחלקי הקלפים במשחק, ומשימתכם היא לערום את כל החפיסות לערימה גדולה אחת. אתם יכולים לשלוט רק בסדר שבין החפיסות. אסור להכניס או להסיר קלף, וגם אסור לשנות את סדר הקלפים בתוך חפיסה.
לאחר יצירת הערימה, הקלפים יחולקו למהמרים. המהמר ה-$i$ יקבל את הקלפים במקומות $i$, $m+i$, $2m+i$, $\ldots$, $km+i$, $\ldots$ מלמעלה למטה. המהמרים האחרים אינם יודעים שהמהמר ה-$b$ הוא למעשה הבוס שלכם. כדי להבטיח את ניצחונו, כל הקלפים שיקבל הבוס חייבים להיות גבוהים, וכל הקלפים שיקבלו המהמרים האחרים חייבים להיות נמוכים.
מצאו סדר לערימת החפיסות שמקיים דרישה זו, או דווחו שהדבר בלתי אפשרי. אם קיימת תשובה חוקית, דווחו על התשובה הקטנה ביותר בסדר לקסיקוגרפי.
התשובה, אם היא קיימת, היא בבירור תמורה באורך $n$. נאמר שהתמורה $P=p_1,p_2,\ldots,p_n$ קטנה לקסיקוגרפית מהתמורה $Q=q_1,q_2,\ldots,q_n$ אם קיים מספר שלם $t$ כך ש-$p_i=q_i$ לכל $1\le i<t$ וכן $p_t<q_t$.
קלט
כל קובץ בדיקה מכיל מקרה בדיקה אחד בלבד.
השורה הראשונה של הקלט מכילה שלושה מספרים שלמים $n$, $m$ ו-$b$ ($1\le n\le2\times10^5$, $2\le m\le2\times10^5$, $1\le b\le m$), המציינים את מספר החפיסות, מספר המהמרים ואינדקס הבוס, בהתאמה.
ב-$n$ השורות הבאות, השורה ה-$i$ מכילה מחרוזת $s_{i,1}s_{i,2}\cdots s_{i,a_i}$ ($s_{i,j}\in\{0,1\}$, $1\le a_i\le10^6$), המתארת את החפיסה ה-$i$.
מובטח כי:
בכל חפיסה יש לפחות קלף גבוה אחד.
מספר הקלפים הכולל מתחלק ב-$m$.
מספר הקלפים הכולל אינו עולה על $10^6$.
פלט
אם קיימת תשובה חוקית, הדפיסו $n$ מספרים שלמים $d_1,d_2,\ldots,d_n$ המופרדים ברווחים, המציינים את התשובה הקטנה ביותר בסדר לקסיקוגרפי, כאשר $d_i$ הוא אינדקס החפיסה ה-$i$ בערימה מלמעלה למטה.
אם אין תשובה חוקית, הדפיסו רק “-1” (ללא מרכאות).
דוגמאות
קלט 1
5 4 3 0100010 00100 001000100 0010 0100010
פלט 1
2 1 3 5 4
קלט 2
4 2 1 010 10101 010 10101
פלט 2
2 1 4 3
קלט 3
1 5 3 001000010000100
פלט 3
1
קלט 4
2 5 3 01000 00010
פלט 4
-1
קלט 5
1 5 3 11111
פלט 5
-1