33209번 - Banalne Baze 스페셜 저지다국어

Gospodin Trump nedavno je pobijedio na predsjedničkim izborima u SAD-u. Odmah nakon izbora, nazvao je Gospodina Malnara da provjeri hoće li djeca diljem Amerike i dalje moći sudjelovati na COCI-ju – internacionalnoj inačici Hrvatskog Otvorenog Natjecanja iz Informatike.

Formalni dio razgovora u kojem je odlučeno o sudbini mladih informatičara SAD-a i dalje nije poznat javnosti. Međutim, neformalni dio razgovora procurio je u javnost:

Gospodin Malnar: Nego, reci ti meni, što ima novo preko bare, a da se o tome ne piše u vijestima?

Gospodin Trump: Ma ništa posebno, nedavno smo stupili u kontakt s izvanzemaljcima, ali nisu nešto prepametni. Ako dođe do toga, siguran sam da ćemo ih pobijediti u ratu.

Gospodin Malnar: Kako znaš da nisu prepametni?

Gospodin Trump: Presreli smo zadaću iz matematike nekog izvanzemaljskog osnovnoškolca, klinac je napisao da je $20 \cdot 2 = 100$. Ajde što mali ne zna, ali učiteljica je zadatak vrednovala kao točan. Kažem ti, nisu prepametni. . .

Gospodin Malnar: Da nemaju možda ti tvoji izvanzemaljci ukupno četiri pipka na rukama?

Gospodin Trump: Wow, čovječe, kako ti to znaš?

Gospodin Malnar: E moj Donalde, ti si taj koji nije prepametan. . .

Dakako, Gospodin Malnar odmah je primijetio da je izraz $20 \cdot 2 = 100$ ispravan u bazi $4$.

Vaš zadatak ovdje je sličan – za dani izraz oblika $A \cdot B = C$, pronađite neku bazu $b$ u kojoj je taj izraz točan i koja je strogo manja od $10^{19}$.

Ulaz se sastoji od tri retka pri čemu prvi redak opisuje broj $A$, drugi redak opisuje broj $B$, a treći redak opisuje broj $C$ iz teksta zadatka.

Svaki se redak sastoji od:

• Broja $n$ ($1 ≤ n ≤ 10^3$) koji označava broj znamenaka broja.
• $n$ brojeva $d_{n-1}, \dots , d_0$ ($0 ≤ d_i ≤ 2^{30}$, $d_{n−1} \ne 0$) koji označavaju vrijednosti znamenaka broja u bazi $10$. Najznačanija znamenka broja ima vrijednost $d_{n-1}$, a najmanje značajna znamenka ima vrijednost $d_0$.

Test podaci će biti takvi da će izraz $A \cdot B = C$ ili biti neispravan u svakoj mogućoj bazi ili će najmanja baza za koju taj izraz vrijedi biti strogo manja od $10^{19}$.

U jedini redak ispišite traženu bazu $b$ ($b < 10^{19}$) iz teksta zadatka. Ako takva baza ne postoji, ispišite riječ impossible, a ako postoji više takvih baza, ispišite bilo koju.

Pojašnjenje drugog probnog primjera:

$$(2 \cdot 13^0 + 1 \cdot 13^1 + 5 \cdot 13^2 ) \cdot (3 \cdot 13^0 + 11 \cdot 13^1 ) = 6 \cdot 13^0 + 12 \cdot 13^1 + 1 \cdot 13^2 + 5 \cdot 13^3 + 4 \cdot 13^4$$