Several men and women are going to attend the singles mixer (聯誼會) tonight. As the organizer, you have collected the personal score of each participant. Several independent events will occur during the party. Each event has a random lucky value ei. If the sum of the scores of a man and a woman equals ei, they will form a perfect pair and dance together. However, since this is a singles mixer and the events are independent, a specific man/woman may dance with a different woman/man in a different event.
Your staff has shown you the lucky value of each event. To gain more control over the party, you want to calculate the number of perfect pairs in each event before the singles mixer.
The first line contains 3 positive integers M, W and E, where there're M men, W women and E events.
The second line contains M integers, denoting the personal score of each man.
The third line contains W integers, denoting the personal score of each woman.
Next, followed by E lines, each line has the lucky score ei.
Testcases:
Cases 1~3: the score of every man or woman is different, 0 < M + W <= 200000, min(M, W) * log2(max(M, W)) * E <= 108
Case 4: 0 <= score, ei <= 100000, 0 < M + W <= 200000, min(M, W) * log2(max(M, W)) * E <= 108
Case 5: 0 < M + W <= 200000, min(M, W) * log2(max(M, W)) * E <= 108
The absolute values of all scores range in [0, 107).
For each event, print the number of perfect pairs. Remember to add a '\n' at the end.