Ngọc Anh vừa tốt nghiệp một khóa học kiến trúc và ngay lập tức, cô ấ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 Ngọc Anh đã 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. Ngọc Anh đặ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ủ, Ngọc Anh 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 Ngọc Anh đã nhờ Hải "dớ" xử lí hộ Ngọc Anh vấn đề này để Ngọc Anh 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