Có \(n\) đồ vật được đánh số từ 1 đến \(n\), đồ vật \(i\) có trọng lượng \(w_i\) và có giá trị là \(v_i\).

An có một cái túi có thể chứa được các đồ vật có tổng khối lượng không quá \(k\). Vì số lượng đồ vật và trọng lượng các đồ vật là rất lớn do đó, nên để tìm được cách chọn đồ vật có tổng khối lượng không vượt quá \(k\) và có tổng giá trị là lớn nhất, An thực hiện một cách như sau:

• Bỏ qua \(t\) đồ vật đầu tiên, hay bỏ qua các đồ vật có chỉ số từ \(1\) đến \(t\);

• Xét lần lượt các đồ vật từ \(t+1\) đến \(n\), xét đến đồ vật \(i\), nếu trọng lượng của đồ vật \(i\) khi thêm vào túi mà không làm quá sức chứa của túi thì sẽ thêm đồ vật \(i\) và túi, ngược lại bỏ qua đồ vật \(i\) và xét đến đồ vật tiếp theo.

Vì không biết giá trị \(t\) nào mà với cách làm trên cho phép An chọn được các đồ vật có tổng giá trị lớn nhất, do đó An quyết định tính toán giá trị của các đồ vật lấy được với \(t\) từ \(0\) đến \(n-1\).

Yêu cầu: Hãy giúp An tìm các giá trị này.

Input

• Dòng đầu chứa hai số nguyên \(n,k (1≤n≤2×10^5;1≤k≤10^9)\)

• Dòng thứ hai chứa \(n\) số nguyên \(v_i (1≤v_i≤10^9)\)

• Dòng thứ ba chứa \(n\) số nguyên \(w_i (1≤w_i≤10^9)\)

Output

• Ghi ra \(n\) số nguyên tương ứng là tổng giá trị của các đồ vật lấy được với \(t\) lần lượt từ \(0\) đến \(n-1\).

Ràng buộc

• Subtask 1: (15%): \(n≤1000\)

• Subtask 2: (20%): \(k≤100\)

• Subtask 3: (20%): \(w_i≤w_{i+1}\)

• Subtask 4: (45%): không có ràng buộc gì thêm

Sample Input

3 15
7 5 9
10 8 6

Sample Output

7 14 9

Sample Input

2 2
1 2
2 1

Sample Output

1 2