After a brilliantly perfomed operation Stirlitz is able to determine the strength of the fascist army. Naturally this information is waited in the headquarters of the Soviet army for already four years. To communicate with the staff Stirlitz uses \textbf{n} wireless operators. Each radio operator must pass a message from Shtirlits to headquarters. Stirlitz as a cunning spy, encrypt the message this way: for each radio operator he give the same number - the size of the army in their number system in such a way that all the number system bases at wireless operators are pairwise coprime. After the transfer of radiograms Mueller bloodhounds were able to identify the last character of each message. You work full-time programmer and need to determine the minimum number that can be send by Stirlitz in his message. Mueller does not like binary code, so he wants you to print the desired number in the decimal notation. \InputFile The first line contains number \textbf{n} - the number of radio operators Shtirlits has. The next line contains \textbf{n} numbers \textbf{a_i} - the base number system, which gave the message Stirlitz radio operators (\textbf{2} ≤ \textbf{a_i} ≤ \textbf{36} ). In the third line of space-separated \textbf{n} symbols \textbf{c_i} - the last letter of each of the messages (\textbf{0} ≤ \textbf{c_i} < \textbf{a_i}; \textbf{c_i} - any number from \textbf{0} to \textbf{9} or letter \textbf{A} through \textbf{Z}). \OutputFile Print the minimum number that can transfer Stirlitz in the decimal system.