PCLNMBR - Peculiar Number


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

He calls it ‘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 <= 103) and (1 <= M <= 105) constraints hold.

M denotes the number of queries.

Each of the next M line contains an integer N (1 <= N <= 109).

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)


hide comments
anirudnits: 2018-10-29 10:14:47

similar problem THREENUMBERS, enjoy:)

:D: 2018-10-25 18:54:29

re Sushovan Sen: any combination of numbers A, B and C from range [1;1000] is valid. It can be show that this guarantees peculiar number sequence will be always infinite and for n <= 10^9 number will fit into 64-bit integers.

re pavan26: I think the optimal solution is O(1) per test case, using some basic math calculations. It's fairy simple, although still proved to be a little more difficult than I initially anticipated. Binary search can also be used, but I think it would be harder to code.

mag1x_: 2018-05-24 19:21:07

@Md. Najim Ahmed
my submit id is 21719918, can you give hint which test case its giving WA for?

pavan26: 2017-02-05 08:15:28

Solution Accepted but Didn't use binary search can anyone tell how to solve using binary search.

xncrpt: 2016-08-15 17:12:02

great problem bro .. :)

Sushovan Sen: 2016-04-18 13:40:09

Is case 4 2 3 3 valid?

gomathi ganesan: 2016-01-03 09:05:38

Not even getting correct answer for the given test cases.....
@Md.Najim Ahmed Is my code completely wrong?

Vipul Srivastava: 2015-12-10 17:18:09

By the way nice problem.

Vipul Srivastava: 2015-12-10 17:17:29

I think the time should be adjusted for different languages accordingly if there is such an option as the logic should be given importance to and not the language


Added by:Md. Najim Ahmed
Date:2015-12-10
Time limit:1.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY