You have two variables a and b. Consider the following sequence of actions performed with these variables:
If a?=?0 or b?=?0, end the process. Otherwise, go to step 2;
If a?≥?2·b, then set the value of a to a?-?2·b, and repeat step 1. Otherwise, go to step 3;
If b?≥?2·a, then set the value of b to b?-?2·a, and repeat step 1. Otherwise, end the process.
Initially the values of a and b are positive integers, and so the process will be finite.
You have to determine the values of a and b after the process ends.
Input
The only line of the input contains two integers n and m (1?≤?n,?m?≤?1018). n is the initial value of variable a, and m is the initial value of variable b.
Output
Print two integers — the values of a and b after the end of the process.
Examples
inputCopy
12 5
output
0 1
inputCopy
31 12
output
7 12
Note
Explanations to the samples:
a?=?12, b?=?5 a?=?2, b?=?5 a?=?2, b?=?1 a?=?0, b?=?1;
a?=?31, b?=?12 a?=?7, b?=?12.
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
int main()
{ll a,b;int num=1;scanf("%lld%lld",&a,&b);while(a!=0&&b!=0){num=1;if(a>=2*b){a=a%(2*b);}else if(b>=2*a){b=b%(2*a);}elsebreak;}printf("%lld %lld",a,b);return 0;
}