Welcome Home Banner

Bessie is returning from a long trip abroad, and Farmer John wants to hang a nice Welcome Home banner in her pasture. The pasture is represented as a grid of posts at all integer coordinate points ranging from (0,0) to (W,H), where the pasture size is W × H. Farmer John will choose two distinct posts to attach the endpoints of a wire. The length of the wire must lie in the range \(L_1\) to \(L_2\) (inclusive), i.e. \(L_1 \leq \text{length} \leq L_2\). Note that \(1 \leq L_1 \leq L_2 \leq 1500\), and \(1 \leq W, H \leq 1000\).

However, to avoid interference, no other post is allowed to lie directly on the straight line segment (the "tight wire") between the two chosen posts. In other words, if the two endpoints are \((x_1,y_1)\) and \((x_2,y_2)\), then there should be no other post collinear with them that lies strictly between them. It is well known that a line segment between two lattice points contains other lattice points if and only if \(\gcd(|x_2-x_1|,|y_2-y_1|) > 1\).

Your task is to determine the number of valid pairs of posts between which Farmer John can hang the banner. Because the answer can be huge, use a 64-bit integer type (or equivalent) to store the result.

Note on Distance Calculation: The distance between two posts \((x_1,y_1)\) and \((x_2,y_2)\) is \(\sqrt{(x_2-x_1)^2 + (y_2-y_1)^2}\). We require that \(L_1^2 \leq (x_2-x_1)^2 + (y_2-y_1)^2 \leq L_2^2\).

inputFormat

The input consists of a single line containing four space-separated integers: W H L1 L2, where the pasture has dimensions W and H, and the allowed wire length is in the range \(L_1\) to \(L_2\) (inclusive).

outputFormat

Output a single integer, the number of valid pairs of posts between which the banner can be hung.

sample

2 1 2 3

2