تُعطى لك الأعداد الصحيحة $n, m, k$ ومتتالية تتكون من $n$ من الأعداد الصحيحة $a_i \in [1, m]$. يمكنك على الأكثر مرة واحدة اختيار فترة من المتتالية (متتالية فرعية متجاورة) طولها $k$ وحساب متوسطها، أي استبدال عناصر هذه الفترة بمتوسطها الحسابي. تستغرق هذه العملية $1$ وحدة زمنية، ويتغير كل عنصر في الفترة بانتظام وبسرعة ثابتة. على سبيل المثال، الفترة ذات العناصر $(3, 9, 5, 1)$ لها متوسط قدره $\frac{3+9+5+1}{4} = 4\frac{1}{2}$، لذا بعد الزمن $t = \frac{2}{3}$ تصبح القيم $(4, 6, 4\frac{2}{3}, 3\frac{1}{3})$، وبعد الزمن $t = 1$ تصبح $(4\frac{1}{2}, 4\frac{1}{2}, 4\frac{1}{2}, 4\frac{1}{2})$. وبشكل رسمي، بعد الزمن $t \in [0, 1]$، فإن العنصر ذا القيمة الابتدائية $a$ يساوي $a' = \bar{a} \cdot t + a \cdot (1 - t)$، حيث $\bar{a}$ هو متوسط الفترة. تتغير فقط العناصر الموجودة في الفترة المختارة.

بشكل مستقل لكل عدد $x$ من $1$ إلى $m$، مهمتك هي تحديد مدى سرعة ظهور القيمة $x$ في أي مكان في المتتالية، من خلال إجراء عملية حساب متوسط فترة ما. بعد كم من الوقت يكون هذا ممكناً؟ اطبع -1 إذا لم يكن من الممكن الحصول على العدد $x$.

الإدخال

يحتوي السطر الأول على ثلاثة أعداد صحيحة $n$ و$m$ و$k$ ($1 \le k \le n \le 300\,000$؛ $1 \le m \le 500\,000$)، تمثل على التوالي طول المتتالية، والحد الأعلى للقيم، وطول الفترة المعدلة.

يحتوي السطر الثاني على $n$ من الأعداد الصحيحة $a_1, a_2, \dots, a_n$ ($1 \le a_i \le m$).

الإخراج

اطبع $m$ من الأسطر. في السطر الـ $x$، اطبع الحد الأدنى للوقت المطلوب (عدداً حقيقياً) اللازم للحصول على العدد $x$، أو اطبع العدد الصحيح -1 (بدون نقطة عشرية) إذا لم يكن ذلك ممكناً باستخدام عملية حساب متوسط واحدة على الأكثر.

الخطأ المطلق المقبول هو $10^{-9}$. يمكنك طباعة ما يصل إلى $20$ رقماً بعد الفاصلة العشرية.

أمثلة

الإدخال 1

8 10 4
3 9 5 1 1 1 1 10

الإخراج 1

0.0000000000
0.2857142857
0.0000000000
0.3333333333
0.0000000000
0.5925925926
0.4000000000
0.2000000000
0.0000000000
0.0000000000

الإدخال 2

1 3 1
2

الإخراج 2

-1
0.0000000000
-1

ملاحظة

في الاختبار الأول، يمكننا حساب متوسط فترة واحدة طولها $k = 4$. النتائج الدقيقة هي $0, \frac{2}{7}, 0, \frac{1}{3}, 0, \frac{16}{27}, \frac{2}{5}, \frac{1}{5}, 0, 0$.

يمكن الحصول على العدد $x = 6$ في أقرب وقت عند الزمن $t = \frac{16}{27} \approx 0.5926$، عن طريق حساب متوسط الأعداد الأربعة الأخيرة $(1, 1, 1, 10)$ إلى المتوسط $\frac{13}{4} = 3\frac{1}{4}$. يكون العنصر الأخير عندئذٍ مساوياً لـ $3\frac{1}{4} \cdot \frac{16}{27} + 10 \cdot \frac{11}{27} = 6$.

يمكن الحصول على العدد $x = 7$ في أقرب وقت عند الزمن $t = \frac{2}{5}$، عن طريق حساب متوسط الفترة $(9, 5, 1, 1)$ إلى المتوسط $4$. يكون الأول من هذه العناصر عندئذٍ مساوياً لـ $4 \cdot \frac{2}{5} + 9 \cdot \frac{3}{5} = 7$.

في الاختبار الثاني، حساب متوسط عنصر واحد لا يغير قيمته. النتيجة لـ $x = 2$ هي $t = 0$، بينما العددان $1$ و$3$ لا يمكن الوصول إليهما.