Середнє останніх N

Сервер отримує послідовність запитів. Кожен запит — це дійсне число, результат обчислення. Після кожного запиту потрібно повертати середнє значення останніх не більше ніж N чисел.

Вхідні дані

Перший рядок містить одне ціле число N (1 ≤ N ≤ 10⁵) — максимальна кількість останніх значень, які враховуються при обчисленні середнього.

Другий рядок містить одне ціле число Q (1 ≤ Q ≤ 10⁵) — кількість запитів.

Далі йдуть Q рядків, у кожному з яких — одне дійсне число xᵢ (-10⁶ ≤ xᵢ ≤ 10⁶) з точністю до 6 знаків після коми.

Вихідні дані

Виведіть Q рядків — середнє значення останніх не більше ніж N чисел після кожного запиту. Відповіді виводьте з точністю не менше ніж 6 знаків після коми.

Приклад

Вхідні дані:

3
5
1.0
2.0
3.0
4.0
5.0

Вихідні дані:

Пояснення:

Після першого: [1.0] → 1.0
Після другого: [1.0, 2.0] → 1.5
Після третього: [1.0, 2.0, 3.0] → 2.0
Після четвертого: [2.0, 3.0, 4.0] → 3.0
Після п’ятого: [3.0, 4.0, 5.0] → 4.0

Average of the Last N

The server receives a sequence of requests. Each request is a floating-point number representing the result of a computation. After each request, you must return the average of no more than the last N numbers.

Input

The first line contains an integer N (1 ≤ N ≤ 10^5) — the maximum number of recent values to consider when computing the average.

The second line contains an integer Q (1 ≤ Q ≤ 10^5) — the number of requests.

The next Q lines each contain a floating-point number xᵢ (-10^6 ≤ xᵢ ≤ 10^6) with up to 6 digits after the decimal point.

Output

Print Q lines — the average of no more than the last N values after each request. Each answer must be printed with at least 6 digits after the decimal point.

Example

Input:

3
5
1.0
2.0
3.0
4.0
5.0

Output:

Explanation:

After first: [1.0] → 1.0
After second: [1.0, 2.0] → 1.5
After third: [1.0, 2.0, 3.0] → 2.0
After fourth: [2.0, 3.0, 4.0] → 3.0
After fifth: [3.0, 4.0, 5.0] → 4.0

DScheglov/average-of-last-n-ukr.md