Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

United State of Koanhali

By Riaz_BSMRSTU · 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

Discussion

Statistics


71% Solution Ratio

masud_ali58Earliest, 1M ago

EgorKulikovFastest, 0.0s

kazi_ruetLightest, 1.7 MB

Tahmid690Shortest, 342B

Submit

Login to submit