Giao dịch khoáng sản

Trong một thế giới vũ trụ khác, có một dải mỏ khoáng sản liên tiếp gồm \(n\) khu vực, được đánh số từ \(1\) đến \(n\). Tại mỗi khu vực thứ \(i\), một công ty khai thác có thể thu được lợi nhuận là \(p_i\). Giá trị này có thể âm nếu chi phí khai thác cao hơn giá trị khoáng sản.

Có \(m\) tập đoàn thương mại đến tìm kiếm các hợp đồng khai thác. Mỗi tập đoàn thứ \(k\) đề nghị mua khoáng sản từ một dãy các khu vực liên tiếp, nhưng phải bao gồm tất cả các khu vực từ \(l_k\) đến \(r_k\) (\(1 \le l_k \le r_k \le n\)). Điều này có nghĩa là, nếu công ty chấp nhận lời đề nghị của tập đoàn \(k\), họ phải chọn một dãy khu vực liên tiếp từ \(x_k\) đến \(y_k\) sao cho \(1 \le x_k \le l_k \le r_k \le y_k \le n\).

Mục tiêu của công ty là tối đa hóa lợi nhuận trung bình trên mỗi khu vực được khai thác. Lợi nhuận trung bình của việc khai thác từ khu vực \(u\) đến \(v\) được tính là \(\frac{p_u + p_{u+1} + \dots + p_v}{v - u + 1}\). Công ty muốn tìm cách khai thác tối ưu cho mỗi lời đề nghị, sau đó so sánh để chọn ra hợp đồng tốt nhất.

Yêu cầu: Cho \(n\) giá trị lợi nhuận \(p_1, p_2, \ldots, p_n\) và \(m\) cặp \((l_1, r_1), (l_2, r_2), \ldots, (l_m, r_m)\). Với mỗi lời đề nghị, hãy xác định cách khai thác mang lại lợi nhuận trung bình trên mỗi khu vực là lớn nhất.

Input

• Dòng đầu tiên chứa một số nguyên dương \(q\) (\(1 \le q \le 1000\)) là số lượng bộ dữ liệu. Tiếp theo là \(q\) nhóm dòng, mỗi nhóm là dữ liệu của một bộ dữ liệu theo khuôn dạng:

• Dòng đầu chứa một số nguyên dương \(n\) là số khu vực;

• Dòng thứ hai chứa \(n\) số nguyên \(p_1, p_2, \ldots, p_n\) (\(0 \le |p_i| \le 4 \cdot 10^6\)) lần lượt là lợi nhuận của các khu vực.
• Dòng thứ ba chứa một số nguyên dương \(m\) là số lời đề nghị;

• Trong \(m\) dòng cuối cùng, dòng thứ \(k\) chứa hai số nguyên \(l_k\) và \(r_k\) (\(1 \le l_k \le r_k \le n\)).

• Tổng giá trị của \(n\) trong mỗi file input không quá \(10^6\). Tổng giá trị của \(m\) trong mỗi file input không quá \(5 \cdot 10^5\).

Output

• Với mỗi bộ dữ liệu, in ra \(m\) giá trị lợi nhuận trung bình lớn nhất tương ứng với \(m\) lời đề nghị. Do các giá trị này là số hữu tỉ, cần in ra dưới dạng số thực và có sai số không quá \(10^{-4}\). Mỗi giá trị được in trên một dòng.

Example

1
7
4 2 -5 3 7 -8 -10
3
3 4
6 6
1 7

2.2000000000
0.6666666667
-1.0000000000

Scoring

Gọi \(N\) là tổng các số \(n\) trong \(q\) bộ dữ liệu, \(M\) là tổng các số \(m\) trong \(q\) bộ dữ liệu.

• Subtask 1 (10 điểm): \(N \le 100\) và \(M \le 100\).
• Subtask 2 (12 điểm): \(N \le 2000\) và \(M \le 10^5\).
• Subtask 3 (14 điểm): \(N \le 50000\) và \(M \le 50\).
• Subtask 4 (20 điểm): \(N \le 50000\) và \(M \le 50000\).
• Subtask 5 (30 điểm): \(N \le 10^6\) và \(M \le 10^5\).
• Subtask 6 (14 điểm): \(N \le 10^6\) và \(M \le 5 \cdot 10^5\).