Tối hôm đi Hội An, cả đám lao vào sinh test cho đề tới 5-6h sáng. Trong lúc đó, cả đám vừa sinh test, vừa code chéo cho nhau.

Trong số đống bài tập đó, anh sẽ cho các bạn thử một bài tập không nằm trong kho đề vì anh mới bịa ra cách đây vài tiếng như sau:

Cho dãy \(A\) có \(n\) số \(A_1, A_2, \dots, A_n\). Xét các đoạn độ dài \(k\).

Có \(q\) câu hỏi, mỗi câu hỏi gồm một số \(X\) \((1 \le X \le 10^{18})\) và có dạng:

Tìm đoạn \((l, r)\) thỏa mãn \(1 \le l \le r \le n\) và \(r-l+1=k\), sao cho tổng \(A_l + A_{l+1} + A_{l+2} + \dots + A_r \le X\), và tổng này là lớn nhất.

Nếu không có đoạn nào thỏa mãn, đáp án sẽ là \(l=r=0\). Nếu có nhiều hơn một đoạn thỏa mãn, ta chọn đoạn có vị trí \(l\) nhỏ nhất

Hãy trả lời \(q\) câu hỏi đó

Input (unreal.inp)

• Dòng đầu tiên chứa hai số \(n, k\)
• Dòng thứ hai chứa \(n\) số \(A_1, A_2, \dots, A_n\).
• Dòng thứ ba chứa một số duy nhất \(q\)
• Dòng cuối cùng chứa \(q\) số, số thứ \(i\) cho biết số \(X\) của truy vấn thứ \(i\)

Output (unreal.out)

In ra \(q\) dòng, dòng thứ \(i\) gồm lần lượt hai số \(l_i, r_i\) cho biết đoạn đáp án của truy vấn \(i\) nằm từ vị trí \(l_i\) tới \(r_i\).

Subtask

• Subtask 1 (30%): \(n, k \le 10^3; q = 1\)
• Subtask 2 (20%): \(n, k \le 10^3; q = 10^5\)
• Subtask 3 (30%): \(n, k \le 10^5; q = 1\)
• Subtask 4 (20%): \(n, k \le 10^5; q = 10^5\)

Sample

5 3
2 1 3 1 2
3
4
5
6

0 0
2 4
1 3