تقف أبقار Farmer John البالغ عددها $N$ ($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