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

Euler Function


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.


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).


Printthe minimumnumberthatcan transfer Stirlitzin the decimalsystem.

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