\textit{Посящается лектору второго дня Харьковской Зимней Школы 2011 по программированию }\textit{\textbf{Дмитрию Жукову}}\textit{.} \includegraphics{https://static.e-olymp.com/content/46/46a44d5e44e2eb8ca5d57c3d219c6a8aa2f0d52f.jpg} Когда Андрей внимательно слушал лекцию Дмитрия Жукова, в зале послышалась фраза “Бабочки Фурье”, от которой Андрей содрогнулся и задумался: "\textit{…на улице конец февраля и минус }\textit{\textbf{25}}\textit{, когда же наконец наступит весна и появятся бабочки?"} От мыслей о предстоящей весне, тепле и бабочках он перестал внимательно слушать лектора и так и не понял алгоритм Карацубы. По приезде домой он спросил учителя: -- \textit{А что это за бабочки Фурье?} ­-- \textit{Послушай, я тебе лучше расскажу о других бабочках, о которых мне рассказывал мой преподаватель, когда я был чуть постарше чем ты и учился в ВУЗе. Может быть они смогут тебе как-то помочь, когда ты будешь самостоятельно разбираться дома с лекцией Дмитрия Жукова…} Алгоритм расчитан на быстрое умножение в уме \textbf{2}-х \textbf{n}-значных чисел. Запишем на доске два \textbf{n}-значных числа (понятно, что если одно из чисел короче -- мы можем спереди дописать нужное нам количество не значущих нулей). Вспомним фразу: "\textit{С младших классов мы знаем табличку умножения}". Что означает эта фраза с точки зрения программиста? А означает она то, что мы можем создать двумерный массив, куда занести табличку умножения для цифр от \textbf{0} до \textbf{9} и при выполнении дальнейших вычислений не умножать заново две цифры, а взять готовое число из памяти -- мы ведь уже знаем табличку умножения!!! Тогда правила для быстрого умножения \textbf{n}-значных чисел можно записать следующим образом: ­Для однозначных чисел правило называется \textbf{I} -- мы умножаем две цифры одна над другой. \includegraphics{https://static.e-olymp.com/content/59/59478eb6d63e259fa72725ae39549502447ebe12.jpg} Для двузначных чисел правило называется \textbf{IXI}. Заметим, что все правила выполняются справа налево. Покажем, как это правило действует в сравнении с обычным умножением в столбик. Поэтому для начала приведём пример обычного умножения для чисел \textbf{25} и \textbf{37}: Теперь объясним, как мы можем обойтись без промежуточных строк, которые нам потом нужно складывать. Умножим (возьмём с таблички умножения!!!) две правые цифры \textbf{5} и \textbf{7} -- выполним правое \textbf{I}. Последнюю цифру результата \textbf{5} запишем сразу в ответ, а остальные цифры (в данном случае только одна цифра \textbf{3}) перенесём в следующий разряд. Теперь выполним \textbf{X}. Для этого сложим в уме \textbf{2∙7} и \textbf{3∙5} и прибавим перенос \textbf{3}. Получим \textbf{14 + 15 + 3 = 32}. Опять запишем в результат полученную последнюю цифру \textbf{2} и запомним перенос \textbf{3}. Выполним левое \textbf{I}: \textbf{2∙3 = 6}, прибавим к нему перенос \textbf{3} и запишем в результат \textbf{9}. В итоге наша последовательность выполнения действий на доске будет иметь вид, как показано на рисунке ниже и слева. \includegraphics{https://static.e-olymp.com/content/fb/fbd73e0cb02c34f039a73c555adaf0fc21fbd3a9.jpg} Для трёхзначных чисел действует правило \textbf{IXЖXI} и так далее -- на каждом этапе максимальная бабочка имеет на одну пару "крылышек" больше, чем предыдущая. -- \textit{Ну как, Андрей, ты понял как теперь можно быстро умножать длинные числа?} -- \textit{О, конечно -- сейчас реализую и испробую на задачке }"\href{/problems/272}{Произведение}". Алгоритм Андрей реализовал, и задачку сдал, а вот теперь задачка для Вас: какое число было перенесено в алгоритме Андрея на \textbf{k}-том шагу? \InputFile В первых двух строках заданы исходные числа \textbf{A} и \textbf{B} (\textbf{A}, \textbf{B} ≤ \textbf{10^10000}), каждое в своей строке. В третьей строке задано число \textbf{k} (\textbf{1} ≤ \textbf{k} ≤ \textbf{20001}). \OutputFile Единственное число, запомненное для переноса, при выполнении умножения в одну строчку.