Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P185SUMB - ROUND 5B - Haru-chan và kỹ thuật thống kê

Haru-chan hiện đang chuẩn bị học một khóa đầy đủ về Trí tuệ Nhân tạo, và để sẵn sàng cho khóa học này, cô quyết tâm luyện tập nghiêm túc về bộ môn thống kê.

Để giúp đỡ, Aki-kun đã gửi một dãy số A[] có kích thước N, và một phần mềm sẽ tự động gửi truy vấn. Mỗi 15 phút, phần mềm sẽ gửi một truy vấn, dưới dạng 2 số nguyên L, R (1 <= L <= R <= N); và nhiệm vụ của Haru-chan trong mỗi 15 phút đó là tìm ra các giá trị trung bình cộng (mean), trung vị (median), phương sai (variance) và độ lệch chuẩn (standard deviation) của dãy con gồm các phần tử có số thứ tự từ L tới R trên mảng A[].

Tất nhiên, dữ liệu lớn cũng cần phải có một công cụ tốt để xử lý, và chỉ trí tuệ lượng tử của Haru-chan là không đủ. Bạn có thể giúp cô được không? <3

Input

Dòng đầu tiên chứa hai số nguyên N và Q, lần lượt là kích thước của dãy A[] và số truy vấn cần thực hiện trong bài toán (1 ≤ N ≤ 4000, 1 ≤ Q ≤ 10^5).

Dòng thứ hai chứa N số nguyên, là các phần tử A_i của A[] (1 ≤ A_i ≤ 4000).

Q dòng tiếp theo, mỗi dòng gồm 2 số nguyên L, R đại diện cho một truy vấn (1 ≤ L ≤ R ≤ N).

Output

Với mỗi truy vấn bất kỳ, in ra 4 số thực, lần lượt là trung bình cộng, trung vị, phương sai và độ lệch chuẩn của dãy con trên truy vấn tương ứng. Kết quả sẽ được chấp nhận với sai số không vượt quá 10^-6.

Example

Input:
5 2
1 6 9 2 5
1 4
3 5

Output:
4.500000000000 4.000000000000 10.250000000000 3.201562118716
5.333333333333 5.000000000000 8.222222222222 2.867441755681

Ghi chú:

Để tham khảo các khái niệm thống kê, ta có thể xem các trang sau:

https://en.wikipedia.org/wiki/Mean

https://en.wikipedia.org/wiki/Median

https://en.wikipedia.org/wiki/Variance

https://en.wikipedia.org/wiki/Standard_deviation


Được gửi lên bởi:Admin
Ngày:2018-08-03
Thời gian chạy:0.5s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.