После блестяще проведенной операции Штирлиц смог определить численность фашистской армии. Естественно такую информацию уже четыре года как ждут в штабе советской армии. Чтобы общаться со штабом Штирлиц использует n радистов. Каждый из радистов должен передать сообщение от Штирлица в штаб. Штирлиц, как хитрый разведчик, зашифровал свое послание таким образом: каждому из радистов он дал одно и то же число - численность армии, но в своей системе счисления, да еще так, что все основания систем счисления у радистов попарно взаимно простые. После передачи радиограммы ищейки Мюллера смогли определить последний символ каждого из сообщений. Вы работаете штатным программистом и должны определить, какое минимальное число мог послать Штирлиц в своем сообщении. Мюллер в отличие от вас не очень любит бинарный код, поэтому он хочет, чтобы искомое число вы вывели в десятичной системе.

   Входные данные

   В первой строке задается число n - количество радистов у Штирлица. В следующей строке находятся n чисел a_i - основания систем счисления, в которых Штирлиц давал сообщения радистам (2 ≤ a_i ≤ 36 ). В третьей строке через пробел записано n символов c_i - последние буквы каждого из сообщений (0 ≤ c_i < a_i; c_i - либо цифра от 0 до 9, либо буква от A до Z).

   Выходные данные

   Вывести минимальное число, которое мог передать Штирлиц в десятичной системе счисления.