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