Extended Euclid Algorithm




Given positive integers a and b, find the integer solution (x, y) to ax + by = gcd(a, b), where gcd(a, b) is the greatest common divisor of a and b.

Constraints

* 1 ≤ a, b ≤ 109

Input


a b


Two positive integers a and b are given separated by a space in a line.

Output

Print two integers x and y separated by a space. If there are several pairs of such x and y, print that pair for which |x| + |y| is the minimal (primarily) and x ≤ y (secondarily).

Examples

Input

4 12


Output

1 0


Input

3 8


Output

3 -1
#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <unordered_map> 
#include <unordered_set>
#include <functional>

using namespace std;

typedef pair<long long int, long long int> P;
typedef tuple<int, int, int> T;

long long int INF = 1e18;
long long int MOD = 1e9 + 7;

long long int extGCD(long long int a, long long int b, long long int &x, long long int &y){
	long long int d = a;
	if(b == 0){
		x = 1;
		y = 0;
	}else{
		d = extGCD(b, a % b, y, x);
		y -= a / b * x;
	}
	return d;
}

int main(){
	long long int a, b, x, y, G;
	cin >> a >> b;
	G = extGCD(a, b, x, y);
	cout << x << " " << y << endl;
	return 0;
}
