Three Arrays

Time limit2sMemory limit256 MB

Summary

Given three sorted arrays and a distance d, count triples of elements (one from each array) whose pairwise differences all stay within d.

Level: Medium6 of 10
Topics: Two pointers, Sorting, Brute force, Array
Solved: No attempts yet

Problem

You are given three arrays: $a$ with $n_a$ elements, $b$ with $n_b$ elements, and $c$ with $n_c$ elements. All three arrays are sorted in non-decreasing order. That is, $a_i \le a_{i + 1}$ for every $i$ with $1 \le i < n_a$ , $b_j \le b_{j + 1}$ for every $j$ with $1 \le j < n_b$ , and $c_k \le c_{k + 1}$ for every $k$ with $1 \le k < n_c$ .

Input

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 \le d \le 10^9$ , $1 \le n_a, n_b, n_c \le 5 \cdot 10^5$ ).

The second line contains $n_a$ integers $a_1, a_2, \ldots, a_{n_a}$ : the array $a$ ( $-10^9 \le a_i \le 10^9$ ).

The third line contains $n_b$ integers $b_1, b_2, \ldots, b_{n_b}$ : the array $b$ ( $-10^9 \le b_i \le 10^9$ ).

The fourth line contains $n_c$ integers $c_1, c_2, \ldots, c_{n_c}$ : the array $c$ ( $-10^9 \le c_i \le 10^9$ ).

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

Output

Examples1

Example 1

Input

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

Expected output

15
56