Bajtocja đang lên kế hoạch tấn công Bitocja một lần nữa! Cuộc đổ bộ vào lãnh thổ kẻ thù là nhiệm vụ dành cho những chiến binh thực thụ, vì vậy quân đội đặc nhiệm tinh nhuệ nhất của Bajtocja – Bajtogrom – sẽ tham gia vào chiến dịch này.

Tại buổi họp của tướng Bajtczak, có $n$ người lính đã tập hợp. Nhờ nhiều năm huấn luyện, họ đã nhanh chóng xếp thành một hàng dọc và được đánh số từ trái sang phải bằng các số nguyên từ $1$ đến $n$. Tướng quân muốn chọn một số đơn vị để gửi đến lãnh thổ Bitocja. Là một chiến lược gia tài ba, ông biết rằng các binh sĩ đứng theo thứ tự này không phải là ngẫu nhiên mà dựa trên mối quan hệ thân thiết giữa họ. Do đó, mỗi đơn vị ông chọn phải bao gồm chính xác $k$ người lính đứng ở các vị trí liên tiếp trong hàng. Nhờ vậy, ông có thể chắc chắn rằng các binh sĩ trong cùng một đơn vị sẽ phối hợp tốt với nhau. Tất nhiên, mỗi người lính chỉ có thể thuộc tối đa một đơn vị, nhưng tướng quân không có yêu cầu cụ thể về số lượng đơn vị – ông có thể không chọn đơn vị nào và hủy bỏ cuộc tấn công vào Bitocja (ít nhất là vào lúc này).

Tướng Bajtczak biết rõ năng lực của binh sĩ – mỗi người được mô tả bằng một số nguyên $a_i$. Giá trị này càng cao, người lính đó càng thiện chiến. Số này cũng có thể là số âm, nghĩa là người lính đó có thể sẽ gây cản trở cho chiến dịch.

Tướng quân muốn tối đa hóa tổng giá trị $a_i$ của tất cả những người lính được gửi đi. Tuy nhiên, có một vấn đề nhỏ: có thể xảy ra trường hợp ông phải cử một số người lính đầu hàng ra mặt trận với Intocja và một số người lính cuối hàng đi làm nhiệm vụ tình báo ở Longlongtocja. Khi đó, ông chỉ có thể chọn các đơn vị từ những người lính có vị trí nằm trong đoạn $[l_i, r_i]$.

Hãy giúp tướng quân xem xét các kịch bản khác nhau và tính toán tổng giá trị $a_i$ lớn nhất có thể của những người lính được gửi đi cho mỗi kịch bản.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên $n, k$ và $q$ ($1 \le n, q \le 3 \cdot 10^5$; $1 \le k \le n$), lần lượt là số lượng binh sĩ trong hàng, số lượng binh sĩ trong mỗi đơn vị và số lượng kịch bản mà tướng quân xem xét.

Dòng thứ hai chứa $n$ số nguyên $a_1, \dots, a_n$ ($-10^9 \le a_i \le 10^9$) như đã mô tả trong đề bài.

$q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l_i$ và $r_i$ ($1 \le l_i \le r_i \le n$). Các số này biểu thị rằng trong kịch bản thứ $i$, chỉ có thể gửi những người lính có vị trí nằm trong đoạn $[l_i, r_i]$.

Dữ liệu ra

Với mỗi kịch bản, in ra trên một dòng một số nguyên duy nhất là tổng giá trị $a_i$ lớn nhất của các binh sĩ được gửi đến Bitocja.

Ví dụ

Input 1

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

Output 1

22
20
0
0
22
20
21

Ghi chú

Giải thích ví dụ: Trong kịch bản thứ nhất và thứ năm, tướng Bajtczak nên gửi hai đơn vị gồm các binh sĩ ở vị trí $[1, 2, 3]$ và $[5, 6, 7]$.

Trong kịch bản thứ hai và thứ sáu, tối ưu nhất là tạo một đơn vị gồm các binh sĩ ở vị trí $[3, 4, 5]$.

Trong kịch bản thứ ba và thứ tư, tướng quân không nên tạo đơn vị nào và cân nhắc lại kế hoạch tấn công.

Trong kịch bản thứ bảy, tướng quân nên tạo hai đơn vị gồm các binh sĩ ở vị trí $[1, 2, 3]$ và $[4, 5, 6]$.

Nhiệm vụ con

Trong một số nhóm test, $k \le 30$.