Thuận quyết định làm một thương nhân buôn bán đồ cổ để lo cho gia đình. Anh ấy cần nhập về một lượng hàng hóa để bắt đầu công vịệc buôn bán của mình. Tại chợ có \(n\) món đồ Thuận có thể mua. Thuận có thể chọn mua món đồ thứ \(i\) với giá \(a_{i}\) và cậu ấy có thể bán lại món đồ đó với giá \(b_{i}\).

Việc mua bán ở đây khá thuận lợi. Nhờ uy tín của bản thân, Thuận được các bên cho phép nhận hàng trước. Thuận có thể nhận tiền bán món đồ \(b_{i}\) trước khi bán nó, miễn là sau cùng Thuận có đưa vật phẩm \(i\) cho bên mua. Việc này đảm bảo minh bạch, vì Thuận phải kí hợp đồng rõ ràng với các bên.

Sở dĩ có sự chênh lệch về giá vì Thuận mua và bán ở hai chợ khác nhau.

Trước khi đi chợ và trở thành một thương nhân như kế hoạch, Thuận cần dự trù số tiền mình cần mang theo. Anh đặt ra \(m\) câu hỏi, câu hỏi thứ \(j\) là: "Giả sử rằng Thuận cầm đi \(k_{j}\) đồng, và buôn bán các món đồ theo mức giá như trên, thì cuối cùng Thuận có thể mua được tối đa bao nhiêu món đồ?"

Hãy lập trình để tính đáp án cho câu hỏi trên.

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n, m\) \((n, m \leq 3 \times 10^{5})\) - lần lượt là số món đồ và số câu hỏi
• Dòng thứ hai chứa \(n\) số nguyên \(a_{i}\) \((0 \leq a_{i} \leq 10^{9})\).
• Dòng thứ ba chứa \(n\) số nguyên \(b_{i}\) \((0 \leq b_{i} \leq 10^{9})\).
• Dòng thứ tư chứa \(m\) số nguyên \(k_{j}\) \((0 \leq k_{j} \leq 10^{15})\).

Output

• Với mỗi câu hỏi, in ra đáp án trên một dòng riêng - số món đồ lớn nhất có thể mua.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \times m \leq 10^{7}\).
• Subtask \(2\) (\(40\%\) số điểm): \(a_{i} \geq b_{i}\)
• Subtask \(3\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

7 3
4 3 7 5 5 2 4
1 1 8 1 6 2 5
0 3 7

5
6
7