Tight three-way take: hints, no solution

A film editor has three cameras, each with its own list of marker times in milliseconds, in ascending order. A take is formed by choosing exactly one marker from each camera. A take is tight if the latest of its three times minus the earliest of its three times is at most span.

Count the tight takes. Markers are told apart by their camera and position, so equal times inside one list, or the same time in different lists, give different takes. Return the count as a whole number; it can exceed 32 bits in principle. Aim to do better than trying every combination: the target is close to linear in the total number of markers.

Examples

Input

a = [1, 4, 9], b = [2, 5, 8], c = [3, 6, 10], span = 3

Output

6

Note

Six takes fit, for instance times (1, 2, 3) and (9, 8, 10).

Input

a = [10, 10], b = [10, 10], c = [10, 10], span = 0

Output

8

Note

Every marker is at 10 so all 8 takes are tight at span 0.

Input

a = [1, 2], b = [50, 60], c = [100], span = 5

Output

0

Note

The lists are far apart, so no take is tight.

Constraints

• 0 <= a.length, b.length, c.length <= 10000, each list ascending
• 0 <= time <= 100000, 0 <= span <= 100000
• Equal times are separate markers

Hint 1: a nudge

If you pretend one marker is the earliest of its take, what needs to be true of the two markers chosen from the other lists?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing