Clash!

Bác John chơi một trò chơi thẻ bài. Có $N$ lá bài, mỗi lá có chi phí $a_i$ (tính bằng moolixir). Bác giữ trên tay $H$ lá bài.

Khởi tạo:

• Tay bài chứa các lá $1$ đến $H$
• Hàng chờ rút bài chứa các lá $H+1$ đến $N$ theo thứ tự

Cơ chế chơi:

• Trò chơi bắt đầu tại thời điểm $0$ với $0$ moolixir
• Trước mỗi giây nguyên $t=1,2,3,\dots$, moolixir tăng thêm $1$
• Một lá bài chỉ được chơi khi chi phí không vượt quá moolixir hiện tại (chi phí bị trừ đi)
• Khi chơi một lá, rút lá đầu hàng chờ vào tay, lá vừa chơi đặt cuối hàng chờ

Điều kiện thắng: Có $k$ lá bài được đánh dấu là "điều kiện thắng". Nếu tay bài có ít nhất một điều kiện thắng, lá tiếp theo bắt buộc phải là điều kiện thắng.

Bác John chơi tối ưu. Cho $Q$ truy vấn, mỗi truy vấn là thời điểm $t$ — tìm số điều kiện thắng tối đa có thể chơi trong thời gian $t$.

Dữ liệu vào

• Dòng 1: Hai số nguyên $N$ và $H$ ($2\le N\le 2\times {10}^5$, $1\le H<N$)
• Dòng 2: $N$ số nguyên $a_1,\dots ,a_N$ ($1\le a_i\le {10}^9$)
• Dòng 3: Số nguyên $k$ ($1\le k\le N$)
• Dòng 4: $k$ chỉ số của các lá điều kiện thắng
• Dòng 5: Số nguyên $Q$ ($1\le Q\le 2\times {10}^5$)
• Dòng 6: $Q$ số nguyên $t$ ($1\le t\le {10}^{18}$)

Dữ liệu ra

Với mỗi truy vấn, in ra số điều kiện thắng tối đa có thể chơi.

Ràng buộc

• $2\le N\le 2\times {10}^5$
• $1\le a_i\le {10}^9$
• $1\le Q\le 2\times {10}^5$
• $1\le t\le {10}^{18}$

Ví dụ

Ghi chú

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