eolymp
bolt
Try our new interface for solving problems
Problems

Positive tests

Positive tests

Time limit 2 seconds
Memory limit 128 MiB

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.

Input data

First line contains numbers a and b (1ab10^18 ). Second line contains numbers k and m (0k , m20). Third line contains k integers x[i] (1x[i]10^18 ) - numbers that must divide the positive test. Fourth line contains m integers y[i] (1y[i]10^18 ) - numbers that must not divide the positive test.

Output data

Print the number of positive tests from a to b.

Examples

Input example #1
5 15
1 1
2
4
Output example #1
3
Input example #2
5 15
0 2

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