Positive tests

Positive tests

Virologist Abutalib continues his mathematical calculations. He is looking for effective ways to detect positive or negative tests for coronavirus. Abutalib has tests for coronavirus numbered from a to b. In the course of his calculations, he found out that positive tests satisfy certain conditions. Thus, the test for coronavirus is positive if the serial number of the test is divided by k numbers previously determined by Abutalib, and at the same time, it is not divided by m numbers also previously determined by Abutalib. You should help Abutalib to find how many tests from a to b are positive.


First line contains numbers a and b (1ab1018 ). Second line contains numbers k and m (0k , m20). Third line contains k integers xi (1xi1018 ) - numbers that must divide the positive test. Fourth line contains m integers yi (1yi1018 ) - numbers that must not divide the positive test.


Print the number of positive tests from a to b.

Time limit 2 seconds
Memory limit 128 MiB
Input example #1
5 15
1 1
Output example #1
Input example #2
5 15
0 2

3 5
Output example #2
Input example #3
1 100000
0 0
Output example #3
Author Rashad Mammadov
Source 2019-2020 Azerbaijan Final, June 17