Trade Agreements in Amber
In the country of Amber, trade and financial interactions are quite intricate. When one merchant wishes to trade their goods with another, they must visit the Amber Trade Guild. You might assume that the merchants simply swap their goods and part ways, pleased with their transaction. However, that's not the case! The laws in Amber stipulate that the Trade Guild can profit from a transaction between two merchants, equivalent to the «normalizing coefficient» of one of the merchants, but only if the «normalizing coefficients» of both merchants are identical. Are you unfamiliar with the concept of a «normalizing coefficient» in Amber? That's understandable...
Consider a merchant who is N years old. In their home country, the numeral system P is used for financial dealings. Their «normalizing coefficient» is defined as the sum of the digits of the number N when expressed in the numeral system P. Your task is to write a program that calculates how much the Trade Guild can earn after a transaction between two merchants.
Input
The first line of the input file provides information about the first merchant, consisting of the numbers N1 and P1. The second line provides information about the second merchant, consisting of N2 and P2. Here, N1 and N2 represent the ages of the two merchants who wish to trade (0 ≤ N1, N2 ≤ 2147483647), and P1 and P2 denote the numeral systems used in their respective countries (2 ≤ P1, P2 ≤ 16).
Output
Output the amount the Trade Guild will earn following the transaction between the merchants.