Большие числа для маленького Васи

문제

Васе на день рождения подарили два числа.

Первое число состоит из цифры D, записанной N раз. Второе состоит из той же цифры D, записанной M раз.

Васе числа очень понравилась, и он захотел с ними поиграть. Он решил найти наибольший общий делитель этих двух чисел (как известно, наибольший общий делитель двух чисел равен наибольшему натуральному числу, на которое оба данных числа делятся без остатка). Однако ему не удалось это сделать — числа оказались слишком большими для него. Поэтому он попросил вас помочь ему.

Помогите Васе! Найдите наибольший общий делитель подаренных ему чисел.

입력

Входные данные содержат две строки.

В первой строке записаны два целых числа, разделенные пробелом: N и M (1 ⩽ N, M ⩽ 10¹⁸) — количество цифр в первом и во втором числе соответственно.

Во второй строке записано одно целое число D (1 ⩽ D ⩽ 9) — цифра, из которой состоят Васины числа.

출력

Если в десятичной записи наибольшего общего делителя двух Васиных чисел не более 10⁶ цифр, то необходимо вывести сам наибольший общий делитель. В противном случае нужно вывести 10⁶ его последних цифр. Не следует выводить лидирующие нули.

1 1
1

1