Ограничение по времени выполнения 1 секунда Ограничение по использованию памяти 128 мегабайт Найдите НОД (наибольший общий делитель) двух натуральных чисел.
НОД(a,b)=⎩⎨⎧a,b=0b,a=0НОД(a mod b,b),a≥bНОД(a,b mod a),a<b Входные данные
Два натуральных числа a и b(a,b≤2⋅109).
Выходные данные
Выведите НОД чисел a и b.
Примеры