Chính phủ đã thống kê được trong toàn quốc có \(k\) tổ chức. Các tổ chức được đánh số từ \(1\) đến \(k\), tổ chức \(i\) có \(n_{i}\) thành viên. Với một người có thể không tham gia hoặc tham gia không quá \(d\) tổ chức. Gọi \(s\) là số lượng người tham gia ít nhất một tổ chức, chính phủ muốn ước lượng cận dưới (nhỏ nhất) của giá trị \(s\).

Chính phủ mới thu thập được danh sách gồm \(q\) người rất đặc biệt, họ tham gia các tổ chức có số hiệu liên tiếp nhau. Thông tin thứ \(j\) cho biết người thứ tham gia các tổ chức liên tiếp từ \(L_{j}\) đến \(R_{j}\) .

Yêu cầu: Cho các thông tin khảo sát được, nếu chỉ sử dụng \(t\) thông tin về \(t\) người đặc biệt đầu danh sách, hãy giúp chính phủ xác định được cận dưới của giá trị \(s\) tương ứng với từng giá trị của \(t\).

Input

• Dòng thứ nhất chứa ba số nguyên dương \(k, d\) và \(q\) \((1 \leq d \leq k \leq 10^{5}, 1 \leq q \leq 10^{6})\).
• Dòng thứ hai chứa \(q\) số nguyên dương \(n_{1}, n_{2}, \ldots, n_{k}\) \((1 \leq n_{i} \leq 10^{9})\)
• Dòng thứ \(j\) trong \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(L_{j}, R_{j}\) \((1 \leq L_{j} \leq R_{j} \leq k)\). Dữ liệu đảm bảo hợp lí.

Output

• Ghi ra \(q + 1\) dòng, mỗi dòng chứa một số nguyên là cận dưới của giá trị \(s\) lần lượt với từng giá trị của \(t\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(k = 2, q \leq 100\).
• Subtask \(2\) (\(30\%\) số điểm): \(q \leq 100\).
• Subtask \(3\) (\(20\%\) số điểm): \(L_{j} = R_{j}\).
• Subtask \(4\) (\(20\%\) số điểm): không có rằng buộc gì thêm.

Example

2 1 1
5 6
2 2

11
11

3 3 2
5 6 7
1 1
1 1

7
8
9