e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Euler Function

Eustace-Alex

After abrilliantlyperfomedoperationStirlitz is ableto determine thestrength ofthe fascistarmy.Naturally thisinformation is waitedin the headquarters ofthe Soviet army for already four years.Tocommunicatewith thestaffStirlitzusesnwireless operators.Eachradio operatormustpassa messagefromShtirlits toheadquarters.Stirlitzasa cunningspy,encryptthe messagethis way: for eachradio operator hegivethe samenumber - thesize ofthe army in theirnumber systemin such a waythatall thenumber system bases at wireless operatorsare pairwisecoprime.After thetransfer ofradiogramsMuellerbloodhoundswere able to identifythe lastcharacterof eachmessage.Youworkfull-timeprogrammerandneedto determinethe minimum numberthat can besend by Stirlitzin his message.Muellerdoes not likebinarycode,sohe wantsyou to print the desirednumberinthe decimal notation.

Input

The firstlinecontains numbern -the numberof radio operatorsShtirlits has.The nextline containsn numbersai -the basenumber system,whichgave themessageStirlitzradio operators (2ai36 ). Inthe third line ofspace-separatednsymbolsci -the lastletterof eachof the messages (0ci < ai; ci - anynumber from 0to9orletterA throughZ).

Output

Printthe minimumnumberthatcan transfer Stirlitzin the decimalsystem.

Time limit 1 second
Memory limit 64 MiB
Input example #1
2
6 13
1 B
Output example #1
37
Author A. Milanin