يوجد $N$ مصباح شارع مضاء على طريق يُمثَّل بخط أعداد. مواضع المصابيح من اليسار إلى اليمين هي $A_1<\cdots<A_N$.
نعرّف درجة الظلام في الموضع $x$ بأنها المسافة من ذلك الموضع إلى أقرب مصباح شارع. وهي أصغر الأعداد $N$ التالية: $|A_1-x|,\ldots,|A_N-x|$. يرمز $|\cdot|$ إلى القيمة المطلقة: $|y|:=y$ عندما يكون $y\ge0$، و$|y|:=-y$ عندما يكون $y<0$.
على سبيل المثال، إذا كانت المصابيح $N=3$ في المواضع $A_1=1$ و$A_2=4$ و$A_3=8$، فإن درجة الظلام في كل موضع صحيح من $0$ إلى $10$ تكون كما يلي.
| الموضع | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ |
|---|---|---|---|---|---|---|---|---|---|---|---|
| درجة الظلام | $1$ | $0$ | $1$ | $1$ | $0$ | $1$ | $2$ | $1$ | $0$ | $1$ | $2$ |
| هل يوجد مصباح؟ | O | O | O |
اكتب برنامجًا يحسب درجة الظلام في جميع المواضع الصحيحة البالغ عددها $L+1$ من $x=0$ إلى $x=L$، ويطبع القيم بالترتيب من أصغر قيمة حتى القيمة ذات الرتبة $K$ تصاعديًا.
القيود
- جميع الأعداد المعطاة صحيحة.
- $1\le L\le 1\,000\,000\,000\,000\,000\,000$
- $1\le N\le300\,000$
- $1\le K\le500\,000$
- $K\le L+1$
- $0\le A_1<A_2<\cdots<A_N\le L$
المهام الفرعية
| # | النقاط | الشرط |
|---|---|---|
| 1 | 10 | $N=1$ |
| 2 | 20 | $N\le2\,500$, $L\le2\,500$ |
| 3 | 15 | $2\le N$. العدد $N-1$ يقسم $L$. $A_i=\frac{L}{N-1}\times(i-1)$. |
| 4 | 20 | $L\le5\,000\,000$ |
| 5 | 35 | لا توجد قيود إضافية. |
الإدخال
يحتوي السطر الأول على ثلاثة أعداد صحيحة $L,N,K$ بهذا الترتيب، مفصولة بمسافات.
يحتوي السطر التالي على $N$ عددًا صحيحًا $A_1,\ldots,A_N$ بهذا الترتيب، مفصولة بمسافات.
الإخراج
اطبع الإجابة في $K$ أسطر بدءًا من السطر الأول. يجب أن يحتوي السطر $i$ على درجة الظلام ذات الرتبة $i$ تصاعديًا.
أمثلة
الإدخال 1
10 3 4 1 4 8
الإخراج 1
0 0 0 1
الإدخال 2
4 5 5 0 1 2 3 4
الإخراج 2
0 0 0 0 0
الإدخال 3
7 1 4 3
الإخراج 3
0 1 1 2
الإدخال 4
9 4 10 0 3 6 9
الإخراج 4
0 0 0 0 1 1 1 1 1 1