Дано числа a і b в 31-річній системі числення. Відомо, що a ділиться на b.

Знайдіть останні k цифр частки від ділення a на b (також записаного в 31-річній системі).

Вхідні дані

У першому рядку міститься ціле додатне число a, що складається не більше ніж з мільйона (31-річних) цифр, записане в 31-річній системі числення (цифри від 0 до 9 відповідають самі собі, заголовні букви від A до U відповідають цифрам від 10 до 30) без ведучих нулів. У другому рядку аналогічно записано число b. Гарантується, що a ділиться на b без залишку. У третьому рядку записано число k (1 ≤ k ≤ 104).

Вихідні дані

Виведіть рівно k31-річних цифр - останні k цифр частки. Якщо у частці менше k цифр, доповніть його зліва ведучими нулями. Всі букви, що виводяться, повинні бути великими.