Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3233
Lucky Number

Time Limit: 5 Seconds      Memory Limit: 32768 KB

Watashi loves M mm very much. One day, M mm gives Watashi a chance to choose a number between low and high, and if the choosen number is lucky, M mm will marry him.

M mm has 2 sequences, the first one is BLN (Basic Lucky Numbers), and the second one is BUN (Basic Unlucky Numbers). She says that a number is lucky if it's divisible by at least one number from BLN and not divisible by at least one number from BUN.

Obviously, Watashi doesn't know the numbers in these 2 sequences, and he asks M mm that how many lucky number are there in [low, high]?

Please help M mm calculate it, meanwhile, tell Watashi what is the probability that M mm marries him.

Input

The first line of each test case contains the numbers NBLN (1 <= NBLN <= 15), NBUN (1 <= NBUN <= 500), low, high (1 <= low <= high <= 1018).

The second and third line contain NBLN and NBUN integers, respectively. Each integer in sequences BLN and BUN is from interval [1, 32767].

The last test case is followed by four zero.

The input will contain no more than 50 test cases.

Output

For each test case output one number, the number of lucky number between low and high.

Sample Input

2 1 70 81
2 3
5
0 0 0 0

Sample Output

5

Hint

The lucky numbers in the sample are 72, 74, 76, 78, 81.


Author: OUYANG, Jialin
Source: ZOJ Monthly, August 2009
Submit    Status