Google | Onsite | Count Valid Triples with Absolute Difference Constraints

Problem Description

You are given three sorted arrays A, B, and C, each of size n, and an integer D. The task is to count the number of unique tuples (i, j, k) where:

• i is an index in array A,
• j is an index in array B,
• k is an index in array C,

such that the following conditions are satisfied:

|A[i] - B[j]| ≤ D,  |A[i] - C[k]| ≤ D,  |B[j] - C[k]| ≤ D

Input

• A, B, C: Lists of integers of length n, sorted in non-decreasing order.
• D: An integer representing the maximum allowable absolute difference.

Output

An integer representing the count of all valid tuples (i, j, k) that satisfy the conditions.

Example

Input:
A = [0, 1]
B = [0, 1]
C = [0, 1]
D = 1

Output:
8

Explanation:
The following 8 tuples satisfy the conditions:

• (i=0, j=0, k=0), (i=0, j=0, k=1), (i=0, j=1, k=0), (i=0, j=1, k=1),
• (i=1, j=0, k=0), (i=1, j=0, k=1), (i=1, j=1, k=0), (i=1, j=1, k=1)