Bessie 即将结束漫长的国外旅行返家，Farmer John 想在她的牧场竖起漂亮的“欢迎回家”横幅迎接她。横幅挂在两柱之间的线上，线长范围为 $L1$..$L2$（$1 \le L1 \le L2; L1 \le L2 \le 1,500$）。
牧场大小为 $W \times H$（$1 \le W \le 1,000; 1 \le H \le 1,000$），每个整数坐标点都有一根柱子。Farmer John 从这 $(W + 1) * (H + 1)$ 点中选恰好两点，支撑悬挂横幅的线的两端。
FJ 不希望横幅悬挂时受干扰，要求两柱间拉紧的线正下方不能有柱子。
请帮助求能挂横幅的方法数。他知道数目很大，32 位整数可能不足以计算答案。
如下牧场，$W = 2$，$H = 1$：
* * *
* * *横幅尺寸范围为 $2..3$。共有 $(2+1) * (1+1) = 6$ 点，以及 $\binom{6}{2} = (6*5)/(2*1) = 15$ 对可能的悬线端点：
| $(0,0)-(0,1)$ | $(0,0)-(2,1)$ | $(0,1)-(2,1)$ | $(1,1)-(2,0)$ |
| $(0,0)-(1,0)$ | $(0,1)-(1,0)$ | $(1,0)-(1,1)$ | $(1,1)-(2,1)$ |
| $(0,0)-(1,1)$ | $(0,1)-(1,1)$ | $(1,0)-(2,0)$ | $(2,0)-(2,1)$ |
| $(0,0)-(2,0)$ | $(0,1)-(2,0)$ | $(1,0)-(2,1)$ |
只有四对线长在 $2..3$ 范围：
| 长度 | 长度 | ||
|---|---|---|---|
| $(0,0)-(2,0)$ | $2.00$ | $(0,1)-(2,0)$ | $2.24$ |
| $(0,0)-(2,1)$ | $2.24$ | $(0,1)-(2,1)$ | $2.00$ |
其中 $(0,0)-(2,0)$ 和 $(0,1)-(2,1)$ 的两端间线上各有一根柱子，故不可用。
所以 15 对中只有两对能挂横幅。
输入格式
- 第 1 行：以空格分隔的四个整数 $W$、$H$、$L1$、$L2$。
输出格式
- 第 1 行：一个整数，表示可能的横幅数量。
样例
输入格式 1
2 1 2 3
输出格式 1
2
题目作者：Nathan Pinsker，2010