נתונים לכם מספרים שלמים $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$ אינם ברי השגה.