Nông dân John đang chơi một trò chơi bài chiến thuật nổi tiếng với cô bò Bessie thân yêu. FJ có \(N\) (\(2\le N\le 2\cdot 10^5\)) lá bài, được đánh số từ \(1\) đến \(N\). Nếu FJ muốn đánh lá bài thứ \(i\), lá bài đó tốn \(a_i\) (\(1 \leq a_i \leq 10^9\)) moolixir.

Tại mọi thời điểm, tay bài của FJ luôn gồm \(H\) lá (\(1\le H<N\)). Ban đầu, tay bài gồm các lá từ \(1\) đến \(H\). Những lá còn lại nằm trong một hàng đợi rút bài. Mỗi khi FJ đánh một lá trên tay, anh sẽ rút lá ở đầu hàng đợi lên tay để thay thế, rồi đưa lá vừa đánh xuống cuối hàng đợi. Ban đầu, các lá từ \(H+1\) đến \(N\) được xếp theo đúng thứ tự đó từ đầu đến cuối hàng đợi.

Trong trò chơi này, thời gian được tính bằng số giây nguyên. Trò chơi bắt đầu ở thời điểm \(0\), khi FJ có \(0\) moolixir. Ngay trước mỗi thời điểm nguyên \(t=1,2,3,\dots\), lượng moolixir tăng thêm \(1\). Tại mỗi thời điểm nguyên, FJ có thể chọn đánh một lá trên tay nếu chi phí của nó không vượt quá lượng moolixir hiện có; khi đó, lượng moolixir của FJ giảm đi đúng bằng chi phí của lá bài.

FJ đánh dấu một tập con các lá bài \(s_1,s_2,\ldots,s_k\) làm điều kiện thắng (\(1\le k\le N\), \(1\le s_i\le N\)). Nếu trên tay FJ có ít nhất một lá điều kiện thắng, lá tiếp theo anh đánh bắt buộc phải là một lá điều kiện thắng.

FJ hỏi bạn \(Q\) (\(1\le Q\le 2\cdot 10^5\)) truy vấn. Mỗi truy vấn có dạng: trong vòng \(t\) đơn vị thời gian (\(1\le t\le 10^{18}\)), số lá điều kiện thắng lớn nhất mà FJ có thể đánh xuống là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(H\).

Dòng thứ hai chứa \(N\) số nguyên \(a_1,a_2,\ldots,a_N\).

Dòng thứ ba chứa số nguyên \(k\), là số lá điều kiện thắng.

Dòng thứ tư chứa \(k\) số nguyên phân biệt \(s_1,s_2,\ldots,s_k\).

Dòng thứ năm chứa số nguyên \(Q\).

Mỗi dòng trong \(Q\) dòng tiếp theo chứa một số nguyên \(t\), là thời điểm cần trả lời cho truy vấn tương ứng.

Dữ liệu ra

Với mỗi truy vấn, hãy in ra số lá điều kiện thắng lớn nhất mà FJ có thể đánh xuống trong vòng \(t\) đơn vị thời gian.

Ví dụ

6 3
2 4 3 5 7 6
2
1 4
6
1
2
3
7
10
1000000000000000

0
1
1
2
2
142857142857143

Phân nhóm

• Test 2–3: \(N,Q\le 100\).
• Test 4–5: \(H=1\).
• Test 6–11: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 3, Silver Division — bài gốc tiếng Anh “Clash!”. Tác giả: Chongtian Ma. https://usaco.org/index.php?page=viewproblem2&cpid=1590