### PROBLEM LINK:

**Author:** Misha Chorniy

**Tester:** Alexey Zayakin

**Editorialist:** Oleksandr Kulkov

### DIFFICULTY:

CAKEWALK

### PREREQUISITES:

None

### PROBLEM:

You’re given array D of size N and Q queries X. In each query you have to compute the result of the program

```
read X
for i = 1..N:
X = floor(X / D*)
print X
```

### QUICK EXPLANATION:

You should consider only O(\log X) terms such that D_i eq 1.

### EXPLANATION:

You may keep keep first \min(2\cdot\log_2 X, N) terms of D which aren’t equal one. If there are more non-one terms than X wiil definitely be equal zero at the end of procedure.

### ALTERNATIVE SOLUTION:

You can keep product P of non-one terms of D instead of keeping this terms and divide X by P. But you should check then that you output zero if there are too much such terms.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.