D. Размен по номиналам

В стране $n$ номиналов монет $a_1 < a_2 < \dots < a_n$, причём $a_1 = 1$ и каждый следующий номинал делится на предыдущий нацело. Монет каждого номинала сколько угодно.

Наберите сумму $S$ наименьшим числом монет и выведите, сколько монет каждого номинала для этого нужно.

Первая строка содержит число $n$ ($1 \le n \le 40$).

Вторая строка содержит $n$ номиналов, $1 \le a_i \le 10^{18}$.

Третья строка содержит число $S$ ($1 \le S \le 10^{18}$).

Одна строка из $n$ чисел: количество монет каждого номинала в порядке возрастания номинала.