Nguyên aka Trần Thanh Nguyên vừa tốt nghiệp một khóa học kiến trúc và ngay lập tức, cậu ấy được giao một công việc thiết kế một ngôi nhà. Ngôi nhà đã hoàn thiện, nhưng vốn là một người yêu Toán học nên Nguyên đã cố tình thiết kế cầu thang với các bậc thang có chênh lệch độ cao giữa hai bậc thang khác nhau.

Biết cầu thang có tổng cộng \(n\) bậc thang, bậc thang thứ \(i\) có cao hơn bậc thang thứ \(i-1\) một khoảng \(a_{i}\) đơn vị độ dài. Nguyên đặt ra một câu hỏi: Giả sử bước chân của một người chỉ có thể leo lên bậc thang kế tiếp nếu chênh lệch giữa bậc thang kế tiếp và bậc thang hiện tại không quá \(t\), hỏi người đó có thể leo được tối đa bao nhiêu bậc thang?

Để tính cho cả nhà gia chủ, Nguyên sẽ cần tính bậc thang tối đa có thể leo cho từng người một. Việc này khá tốn thời gian, nên Nguyên đã nhờ bạn xử lí hộ Nguyên vấn đề này để Nguyên có thể đi thiết kế những ngôi nhà khác.

Yêu cầu: Với mỗi người, xác định số bậc thang tối đa họ có thể leo?

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n,m\) (\(n,m \le 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_{1}, a_{2},..., a_{n}\) (\(a_{i} \le 10^9\)).
• Dòng thứ ba chứa \(m\) số nguyên \(t\) (\(t \le 10^9\)).

Output

• Với mỗi người, in ra trên một dòng là số bậc thang tối đa họ có thể leo.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(m \le 100\).
• Subtask \(2\) (\(30\%\) số điểm): \(a_{1} \le a_{2} \le a_{3} \le ... \le a_{n}\).
• Subtask \(3\) (\(30\%\) số điểm): không có ràng buộc gì thêm.

Example

5 2
1 2 2 4 5
2 4

3
4