Thuận là chủ của thương hiệu Mountain Game - chuyên cung cấp dịch vụ leo núi dưới dạng một trò chơi thi đấu. Khu vực tổ chức thi leo núi của Mountain Game có thể được chia thành \(n\) cấp bậc với độ cao tăng dần. Trong đó, \(a_i\) là độ khó khăn để vượt từ cấp \(i-1\) lên cấp \(i\). Ta quy ước cấp \(0\) là mặt đất, nơi mỗi người chơi sẽ bắt đầu.
Theo luật chơi, nếu người chơi hiện đang có mức độ thể lực là \(x\), thì người đó chỉ vượt qua được những cấp bậc có độ khó không lớn hơn \(x\). Việc di chuyển lên các cấp không tiêu hao thể lực.
Sau khi đi tới cấp độ \(i\), bất kì người chơi nào cũng sẽ nhận được một buff hoặc nerf tương ứng, giúp thể lực của người đó giảm đi một lượng \(b_i\), tức là

(nếu \(b_i\) âm, tức thể lực của người chơi được tăng lên - buff). Ta giả sử có vô hạn buff / nerf tại mỗi cấp, nhưng mỗi người chơi khi tiến tới cấp \(i\) sẽ được nhận buff tại tầng đó một lần duy nhất.
Luật chơi cũng giới hạn người chơi di chuyển từ cấp thấp lên cấp cao hơn, lần lượt, tức từ cấp \(i\) lên cấp \(i+1\) theo thứ tự \(1,2,3,\dots,n\).
Ngoài ra, để đảm bảo an toàn, khi một người chơi không thể tiến thêm được nữa (không đủ thể lực hoặc đã ở cấp cuối cùng), trên mỗi cấp đã có bố trí sẵn phòng nghỉ ngơi và cánh cửa thần kì để mỗi người chơi dừng lại và trở về mà không tiêu hao thể lực.
Dĩ nhiên, khi vượt qua một màn với độ khó khăn là \(x\) thì người chơi cũng được thưởng thêm một lượng tiền là \(x\) USD. Phần thưởng này đã thu hút rất nhiều người chơi đăng ký.
Có \(q\) người chơi đã đăng ký Mountain Game, với mỗi người thứ \(j\), Thuận biết được thể lực của người đó là \(k_j\) (theo thông tin đăng ký). Để dự trù kinh phí, Thuận cần tính trước với mỗi người, tổng tiền thưởng cần chuẩn bị cho anh ta là bao nhiêu?

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((1 \leq n,q \leq 5 \times 10^{5})\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n (1 \le a_i \le 10^9)\) là độ khó của các cấp độ.
• Dòng thứ ba chứa \(n\) số nguyên \(b_1, b_2, \dots, b_n (|b_i| \le 10^9)\) là mức độ thay đổi thể lực của từng cấp.
• \(q\) dòng tiếp theo, dòng thứ \(j\) chứa một số \(k_j\) \((1 \leq k_j \leq 10^{15})\) là thể lực của người chơi thứ \(j\).

Output

• Với mỗi người chơi, in ra lượng tiền tối đa của người đó có thể được thưởng, trên một dòng riêng biệt.

Scoring

• Subtask \(1\) (\(24\%\) số điểm): \(n,q \le 5000\).
• Subtask \(2\) (\(24\%\) số điểm): \(b_i = 0\).
• Subtask \(3\) (\(26\%\) số điểm): \(b_i < 0\).
• Subtask \(4\) (\(26\%\) số điểm): không có ràng buộc gì thêm.

Example

3 4
2 3 5
2 -1 1
1
2
5
8

0
2
5
10