URI Online Judge | 2767


By Yuri Cardoso Santamarina, UFU BR Brazil

Timelimit: 1

Joãozinho is organizing his birthday party with N men and M women, and he wants to know the number of good pairs that can be formed with his guests. A pair is good when it is composed of a man and a woman and the sum of the heights of the two persons is multiple of K. The same person can be part of more than one pair.


The input is composed of several test cases and ends with EOF.
The first line of a test case contains the integers N, M and K (\(1 \leq N, M, K \leq 10^5\)). The second line contains N integers Ai, representing the height of the N men invited. The third and last line of the input contains M integers Bi representing the height of the invited women. (\(1 \leq Ai, Bi \leq 10^5\)).


The output should contain one integer for each test case, indicating the number of good pairs that can be formed.

Input Sample Output Sample

3 3 2
1 2 3
4 2 7
2 3 2
1 2
4 2 7