Торгові угоди в Амбері#596
У країні Амбер торгові та фінансові відносини досить складні. Якщо один купець хоче обміняти свої товари на товари іншого купця, вони повинні звернутися до Торгової Гільдії Амбера. Можливо, ви думаєте, що купці просто обміняються товарами й підуть раді після вдалої угоди? Аж ніяк! Закони Амбера вимагають, щоб Торгова Гільдія могла отримати прибуток від угоди між двома купцями лише тоді, коли «нормалізуючі коефіцієнти» обох купців рівні. Ви знаєте, що таке «нормалізуючий коефіцієнт»? Не дивно...
Припустімо, купцеві років. У країні, звідки він походить, для грошових операцій використовують систему числення з основою . «Нормалізуючий коефіцієнт» цього купця визначається як сума цифр числа у системі числення з основою . Напишіть програму, яка визначить, скільки зможе заробити Торгова Гільдія після угоди між двома купцями.
У першому рядку вказано інформацію про першого купця: числа N_1 і P_1. У другому рядку — інформація про другого купця: числа N_2 і P_2. Тут N_1 і N_2 — це вік купців, 0 \leq N_1, N_2 \leq 2147483647. P_1 і P_2 — основи систем числення, якими користуються в їхніх країнах, 2 \leq P_1, P_2 \leq 16.
Виведіть, скільки отримає Торгова Гільдія після угоди між купцями.
Приклад 1