United State of Koanhali

Riaz_BSMRSTU Replay of BSMRSTU Home Qu...
Limits 1s, 512 MB

Koanhali is a strange country. The govt. of Koanhali maintain the marriages of this country. If you want to get married, you have to include yourself in their list. Then, they will find a match for you. If they don't find any match for you, sorry to say, you have to spend the rest of your life alone.

In a few days, govt. of Koanhali decided to hold a draw. They have a list of men and a list of women to find the matches. Every man or woman has a beauty. Govt. have a strange rule to find a match. They will take a man from the man's list and a woman from the woman's list and will make a match if and only if the sum of their beauty is divisible by k. And that's how they keep finding matches until they are unable to find anymore. Now, Govt. of Koanhali hired you to make a program for them so that they can calculate how many matches they have found in total.

You will be given two list. One of them is for men and other is for women. You will also be given the value of k. Your program should find out the total number of matches.

Input

First line will contain three integer n (1 ≤ n ≤ 105), size of the man's list, m (1 ≤ m ≤ 105), size of woman's list and k (1 ≤ k ≤ 106).
Next two line will contain respectively n and m integers, which donates the beauties (1 ≤ beauty ≤ 109).

Output

Print total number of matches they will find.

Sample

InputOutput
3 2 3
1 2 4
2 2
2

Submit

Login to submit.

Statistics

69% Solution Ratio
masud_ali58Earliest, May '20
EgorKulikovFastest, 0.0s
kazi_ruetLightest, 1.7 MB
steinumShortest, 278B
Toph uses cookies. By continuing you agree to our Cookie Policy.