405011: GYM101741 A Three Arrays

You are given three arrays: a containing n_a elements, b containing n_b elements and c containing n_c elements. These arrays are sorted in non-decreasing order: that is, for every i such that 1 ≤ i < n_a we have a_i ≤ a_i + 1, for every j such that 1 ≤ j < n_b we have b_j ≤ b_j + 1, and for every k such that 1 ≤ k < n_c we have c_k ≤ c_k + 1.

Your task is to calculate the number of triples (i, j, k) such that |a_i - b_j| ≤ d, |a_i - c_k| ≤ d, and |b_j - c_k| ≤ d.

The input contains one or more test cases. Each test case consists of four lines.

The first line of each test case contains four integers: d, n_a, n_b, and n_c (1 ≤ d ≤ 10⁹, 1 ≤ n_a, n_b, n_c ≤ 5·10⁵).

The second line contains n_a integers a₁, a₂, ..., a_na: the array a ( - 10⁹ ≤ a_i ≤ 10⁹).

The third line contains n_b integers b₁, b₂, ..., b_nb: the array b ( - 10⁹ ≤ b_i ≤ 10⁹).

The fourth line contains n_c integers c₁, c₂, ..., c_nc: the array c ( - 10⁹ ≤ c_i ≤ 10⁹).

All arrays are sorted in non-decreasing order. The total sum of n_a over all testcases does not exceed 5·10⁵. The total sum of n_b over all testcases does not exceed 5·10⁵. The total sum of all n_c over all testcases does not exceed 5·10⁵. The test cases just follow one another without any special separators.

For each test case, print a single integer: the number of triples (i, j, k) such that |a_i - b_j| ≤ d, |a_i - c_k| ≤ d, and |b_j - c_k| ≤ d.

1 3 3 3
1 2 3
1 2 3
1 2 3
1 6 6 6
1 1 2 2 3 3
2 2 3 3 4 4
3 3 4 4 5 5

15
56