Cả thế giới đang phải chịu ảnh hưởng hết sức nặng nề của một chủng virus mới mang tên "khô bồng". Người bị nhiễm chủng virus này có các biểu hiện như: đi chơi Noel một mình, ngại tiếp xúc với đám đông, ... và đặc biệt là thường xuyên cảm thấy cô đơn, trống vắng trong lòng, mặc cảm với những người xung quanh. Ngoài những ảnh hưởng nặng nề cho người bị nhiễm, loại virus này còn nguy hiểm bởi khả năng lây lan trong vòng ~1~ giây.

Để nghiên cứu và tìm ra vaccine chống lại virus, các nhà khoa học đã mời được ~n~ tình nguyện viên tham gia khảo sát để tìm hiểu quá tính lây lan của nó. Cuộc khảo sát diễn ra trong vòng ~t~ giây, ~n~ tình nguyện viên ngồi trên một chiếc bàn hình tròn đánh số lần lượt từ ~1~ đến ~n~ theo chiều kim đồng hồ. Ban đầu, các nhà khoa học sẽ cho ~m~ người bị nhiễm virus. Sau đó cứ mỗi giây, virus sẽ nhân đôi, tuy nhiên chúng sẽ không ở lại chủ thể cũ mà sẽ lây nhiễm sang hai người là người thứ ~k~ tính từ người ngồi bên trái chủ thể theo chiều kim đồng hồ và người thứ ~k~ tính từ người bên phải chủ thể theo chiều ngược kim đồng hồ.

Hãy giúp các nhà khoa học tính số lượng người bị nhiễm virus "khô bồng" sau khi cuộc khảo sát kết thúc để phát người yêu cho họ.

Input

• Dòng đầu tiên chứa bốn số nguyên ~n~, ~m~, ~k~, ~t~ lần lượt là số tình nguyện viên tham gia khảo sát, số người bị nhiễm bệnh ban đầu, khoảng cách lây lan của virus và thời gian cuộc khảo sát diễn ra ~(1 \leq k < n \leq 10^{18}, 0 \leq t \leq 10^{18}, 1 \leq m \leq min(n, 10^6))~.

• Dòng thứ hai chứa ~m~ số nguyên dương phân biệt ~p_1, p_2, ..., p_n~ là chỉ số của những người bị nhiễm virus ban đầu.

Output

• Một số duy nhất là số người bị nhiễm bệnh sau khi cuộc khảo sát kết thúc.

Subtask

• ~30 \%~ số test có ~n, t \leq 3000~.

• ~30 \%~ số test khác có ~m = 1~.

• ~40 \%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

12 2 1 3
1 8

Sample Output 1

8

Note

Ở giây thứ ~0~, hai người được đánh số ~1~ và ~8~ bị nhiêm bệnh.

Ở giây thứ ~1~, bốn người được đánh số ~2~, ~7~, ~9~ và ~12~ bị nhiễm bệnh.

Ở giây thứ ~2~, sáu người được đánh số ~1~, ~3~, ~6~, ~8~, ~10~, ~11~ bị nhiễm bệnh.

Ở giây thứ ~3~, tám người được đánh số ~2~, ~4~, ~5~, ~7~, ~9~, ~10~, ~11~, ~12~ bị nhiễm bệnh.