Ajoy has got some spare time today. He is using this spare time to think of a particular kind of number.

He calls it a ‘Peculiar Number’.

A peculiar number is define by three integers A, B and C and has the following characteristics:

1. If a number is a multiple of A but not a multiple of B then it is a peculiar number.
2. If a number is a multiple of both A and B then it will be a peculiar number only if it is also a multiple of number C. Otherwise it is not a peculiar number.

Now, Ajoy is trying to find the Nth peculiar number for a fixed A, B and C.

But Ajoy does not have all day. So he needs your help to solve the problem.

Input

First line of the input contains four integers A, B, C  and M where (1 ≤ A, B, C ≤ 10³) and (1 ≤ M ≤ 10⁵) constraints hold.

M denotes the number of queries.

Each of the next M line contains an integer N (1 ≤ N ≤ 10⁹).

Output

For each query, print the Nth peculiar number.

Example

Input #1
3 2 4 3
1
2
3

Output #1
3
9
12

Input #2
983 991 997 3
323233123
2131234
1000000000

Output #2
318058785019
2097116472
983991931538

(set by: Nashir Ahmed)