题目描述

小易学习了转相除法之后，就开始实践这个算法在求解最大公约数上。牛牛给小易出了一道不同寻常的求解最大公约数：求解a和b的最大公约数，但是a和b的范围特别大。 小易遇到了因难，向聪明的你寻求帮助，希望你能帮帮他。

输入描述：

第一行数字 a，第二行数字 b
\(1 \leq a \leq 10^{10^5}, 1 \leq b < 10^{18}\)

输出描述

一行一个数字表示答案

示例 1

输入输出示例仅供调试，后台判题数据一般不包含示例

输入

6
4

输出

2

示例 2

输入输出示例仅供调试，后台判题数据一般不包含示例

输入

7951346523609888
6998915114363550

输出

1013754