$N$ הפרות של Farmer John ($1\le N\le 10^5$) עומדות בשורה. לכל $1\le i\le N$ הפרה ה־$i$ משמאל נושאת את התווית $i$.

Farmer John המציא תרגיל בוקר חדש. הוא נתן לפרות $M$ זוגות מספרים שלמים $(L_1,R_1) \ldots (L_M, R_M)$, כאשר $1 \leq M \leq 100$, ומורה להן לחזור על התהליך הבא, בן $M$ צעדים, בדיוק $K$ פעמים ($1\le K\le 10^9$):

• לכל $i$ מ־$1$ עד $M$:
• הפרות שנמצאות כעת במיקומים $L_i \ldots R_i$ משמאל הופכות את סדרן.

לאחר בדיוק $K$ חזרות, הדפיסו את תווית הפרה ה־$i$ משמאל לכל $1\le i\le N$.

קלט

השורה הראשונה מכילה $N$, $M$ ו־$K$. לכל $1\le i\le M$, שורה $i+1$ מכילה $L_i$ ו־$R_i$, מספרים שלמים בטווח $1 \ldots N$ עם $L_i < R_i$.

פלט

בשורת הפלט ה־$i$ הדפיסו את האיבר ה־$i$ במערך לאחר ביצוע רצף ההוראות $K$ פעמים.

דוגמאות

קלט 1

7 2 2
2 5
3 7

פלט 1

1
2
4
3
5
7
6

הערה

בתחילה הסדר משמאל לימין הוא $[1,2,3,4,5,6,7]$. לאחר הצעד הראשון הוא $[1,5,4,3,2,6,7]$, ולאחר השני $[1,5,7,6,2,3,4]$. ביצוע שני הצעדים פעם שנייה נותן את פלט הדוגמה.

תת־משימות

• מקרה הבדיקה 2 מקיים $N=K=100$.
• מקרי הבדיקה 3-5 מקיימים $K\le 10^3$.
• למקרי הבדיקה 6-10 אין מגבלות נוספות.

מחבר הבעיה: Brian Dean