กำหนดจำนวนเต็ม $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$ ไม่สามารถไปถึงได้