Cho dãy số nguyên \(A=(a_1,a_2,\ldots,a_n)\) với một dãy con khác rỗng gồm các phần tử liên tiếp trong \(A\), ta định nghĩa độ lệch của dãy con đó là hiệu số phần từ lớn nhất trừ phần tử nhỏ nhất trong dãy con.

Yêu cầu: Với số nguyên \(k\), cho biết có bao nhiêu dãy con khác rỗng gồm các phần tử liên tiếp trong \(A\) có độ lệch không quá \(k\).

Để tránh việc phải đọc một lượng dữ liệu quá lớn, dãy \(A\) sẽ được cho bởi 3 số nguyên \(p,q,m\). Mỗi phần tử a_i∈A sẽ được tính bởi công thức:

Ví dụ với \(n=5,p=3,q=0,m=5\), dãy \(A\) sẽ là \((3,1,4,2,0)\).

Input

Vào từ file văn bản SDIFF.INP

• Dòng 1 chứa số nguyên dương \(n \leq 5\cdot 10^6\).
• Dòng 2 chứa 3 số nguyên không âm \(p,q,m \leq 10^9\) \((m>0)\).
• Dòng 3 chứa số nguyên không âm \(k\leq 10^9\).

Output

Ghi ra file văn bản SDIFF.OUT một số nguyên duy nhất là số dãy thỏa mãn yêu cầu đề bài.

Example

5
3 0 5
2

8

Nguồn: Thầy Lê Minh Hoàng