You are given a straight line, $a\cdot x+b\cdot y=c$. Find the point closest to the origin that also satisfies the following properties:  

$\boldsymbol{x}$ and $y$ are integers.  
$\boldsymbol{x}$ is greater than zero.  

If more than one solution exists satisfying $\mbox{1}$ and $2$, then choose the point in which $\boldsymbol{x}$ is minimal.  

Given $\textit{q}$ queries consisting of $a_i$, $b_i$, and $c_i$, find and print the point satisfying the above conditions for each respective query. Each point must be printed on a new line as two space-separated integers denoting the point's respective $x_i$ and $y_i$ values.

Note: It is guaranteed that there will always be integral points on the line.  

Input Format

The first line contains an integer, $\textit{q}$, denoting the number of queries. 

Each line $\boldsymbol{i}$ of the $\textit{q}$ subsequent lines contains three space-separated integers describing the respective values of $a_i$, $b_i$, and $c_i$ for the query.  

Constraints

$1\leq q\leq10^5$  
$1\leq a\leq10^8$  
$1\leq b\leq10^8$  
$1\leq c\leq10^8$  

Output Format

For each query, print $2$ space-separated integers on a new line denoting the respective values of $x_i$ and $y_i$ for the point satisfying the $i^{\mbox{th}}$ query.

Sample Input
1
2 3 1

Sample Output
2 -1

Explanation

Given the line $2\cdot x+3\cdot y=1$, the point $(2,-1)$ is on the line and satisfies the conditions specified above. Thus, we print the coordinate as two space-separated integers on a new line.

Source: hackerrank | Difficulty: MEDIUM
Tags: Geometry


Solutions:
from math import floor

def GCD(a, b):
	if a < b:
		c = a
		a = b
		b = c
	while 1:
		if a % b == 0:
			return b
		c = a % b
		a = b
		b = c

def GCDEx(a, b):
	if b == 0:
		sx = 1
		sy = 0
		return (sx, sy)
	(sx, sy) = GCDEx(b, a % b)
	t = sx
	sx = sy
	sy = t - a // b * sx
	return (sx, sy)

def closest(t):
	if abs(t - floor(t)) > 0.5:
		return floor(t) + 1
	else:
		return floor(t)
q = int(input().strip())
for i in range(q):
	(a, b, c) = [int(x) for x in input().strip().split()]
	gcd = GCD(a, b)
	a = a // gcd
	b = b // gcd
	c = c // gcd
	(sx, sy) = GCDEx(a, b)
	t1 = floor(-sx * c / b) + 1
	t2 = c * (a * sy - b * sx) / (a * a + b * b)
	if t1 >= t2:
		t = t1
	else:
		t = closest(t2)
	print(sx * c + t * b, sy * c - t * a)


from math import floor

def GCD(a, b):
	if a < b:
		c = a
		a = b
		b = c
	while 1:
		if a % b == 0:
			return b
		c = a % b
		a = b
		b = c

def GCDEx(a, b):
	if b == 0:
		sx = 1
		sy = 0
		return (sx, sy)
	(sx, sy) = GCDEx(b, a % b)
	t = sx
	sx = sy
	sy = t - a // b * sx
	return (sx, sy)

def closest(t):
	if abs(t - floor(t)) > 0.5:
		return floor(t) + 1
	else:
		return floor(t)
q = int(input().strip())
for i in range(q):
	(a, b, c) = [int(x) for x in input().strip().split()]
	gcd = GCD(a, b)
	a = a // gcd
	b = b // gcd
	c = c // gcd
	(sx, sy) = GCDEx(a, b)
	t1 = floor(-sx * c / b) + 1
	t2 = c * (a * sy - b * sx) / (a * a + b * b)
	if t1 >= t2:
		t = t1
	else:
		t = closest(t2)
	print(sx * c + t * b, sy * c - t * a)


def dist_to_origin(x, y):
	return x * x + y * y

def extended_gcd(b, n):
	(x0, x1, y0, y1) = (1, 0, 0, 1)
	while n != 0:
		(q, b, n) = (b // n, n, b % n)
		(x0, x1) = (x1, x0 - q * x1)
		(y0, y1) = (y1, y0 - q * y1)
	return (b, x0, y0)

def getyforx(x, a, b, c):
	return (c - a * x) // b
q = int(input().strip())
for _ in range(q):
	(a, b, c) = map(int, input().strip().split(' '))
	(gcd, x, y) = extended_gcd(a, b)
	(a, b, c) = (a // gcd, b // gcd, c // gcd)
	k = c
	(x_point, y_point) = (k * x, k * y)
	x_closest = a * c / (a * a + b * b)
	y_closest = b * c / (a * a + b * b)
	x_diff = x_point - x_closest
	x_steps = int(x_diff // b)
	x_candidate = x_point - x_steps * b
	y_candidate = getyforx(x_candidate, a, b, c)
	while not x_candidate > 0:
		x_candidate += b
	while x_candidate - b > 0:
		x_next = x_candidate - b
		y_next = getyforx(x_next, a, b, c)
		if dist_to_origin(x_next, y_next) < dist_to_origin(x_candidate, y_candidate):
			(x_candidate, y_candidate) = (x_next, y_next)
		else:
			break
	while True:
		x_next = x_candidate + b
		y_next = getyforx(x_next, a, b, c)
		if dist_to_origin(x_next, y_next) < dist_to_origin(x_candidate, y_candidate):
			(x_candidate, y_candidate) = (x_next, y_next)
		else:
			break
	print(int(x_candidate), int(y_candidate))


def extendedEuclidean(a, b):
	(r0, r) = (a, b)
	(s0, s) = (1, 0)
	(t0, t) = (0, 1)
	while r:
		(quot, rem) = divmod(r0, r)
		(r0, r) = (r, rem)
		(s0, s) = (s, s0 - quot * s)
		(t0, t) = (t, t0 - quot * t)
	return (r0, s0, t0, abs(t), abs(s))
q = int(input())
for _ in range(q):
	(a, b, c) = [int(n) for n in input().split()]
	(g, x, y, u, v) = extendedEuclidean(a, b)
	mult = c // g
	x *= mult
	y *= mult
	if x <= 0:
		k = -x // v + 1
		x += k * v
		y -= k * u
	elif x > v:
		k = (x - 1) // v
		x -= k * v
		y += k * u
	(x0, y0) = (x, y)
	d0 = x ** 2 + y ** 2
	while y >= u:
		x += v
		y -= u
		d = x ** 2 + y ** 2
		if d < d0:
			(x0, y0) = (x, y)
			d0 = d
	print(x0, y0)


q = eval(input())

def gcd(a, b):
	s1 = 1
	s2 = 0
	t1 = 0
	t2 = 1
	while a % b != 0:
		q = a // b
		s = s1 - s2 * q
		s1 = s2
		s2 = s
		t = t1 - t2 * q
		t1 = t2
		t2 = t
		c = b
		b = a % b
		a = c
	return (b, s2, t2)
for i in range(q):
	(a, b, c) = map(int, input().split())
	(r, x, y) = gcd(a, b)
	if x < 0:
		x += b // r
		y -= a // r
	x *= c // r
	y *= c // r
	q = x // (b // r)
	x %= b // r
	y += q * (a // r)
	if x == 0:
		x += b // r
		y -= a // r
	search = True
	while search:
		if x ** 2 + y ** 2 > (x + b // r) ** 2 + (y - a // r) ** 2:
			x += b // r
			y -= a // r
		else:
			search = False
	print(x, y)


from math import sqrt
import sys
sys.setrecursionlimit(1000000)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, x, y) = egcd(b % a, a)
		return (g, y - b // a * x, x)

def xgcd(b, n):
	(x0, x1, y0, y1) = (1, 0, 0, 1)
	while n != 0:
		(q, b, n) = (b // n, n, b % n)
		(x0, x1) = (x1, x0 - q * x1)
		(y0, y1) = (y1, y0 - q * y1)
	return (b, x0, y0)
for _ in range(int(input())):
	(a, b, c) = map(int, input().split(' '))
	r = list(egcd(a, b))
	u = a // r[0]
	v = b // r[0]
	l = c // r[0]
	px = r[1] * l
	py = r[2] * l
	mx = a * c / (a ** 2 + b ** 2)
	my = b * c / (a ** 2 + b ** 2)
	kxa = (mx - px) / v
	kya = (py - my) / u
	if int(kxa) == kxa:
		print(int(mx), int(my))
	else:
		if kxa < 0:
			k = int(kxa) - 1
		else:
			k = int(kxa)
		xf1 = px + v * k
		yf1 = py - u * k
		df1 = sqrt(xf1 ** 2 + yf1 ** 2)
		k = int(k + 1)
		xf2 = px + v * k
		yf2 = py - u * k
		df2 = sqrt(xf2 ** 2 + yf2 ** 2)
		if 1:
			if df1 < df2:
				if xf1 > 0:
					print(int(xf1), int(yf1))
				else:
					print(int(xf2), int(yf2))
			elif df1 > df2:
				if xf2 > 0:
					print(int(xf2), int(yf2))
				else:
					print(int(xf1), int(yf1))
			elif xf1 < xf2:
				if xf1 > 0:
					print(int(xf1), int(yf1))
				else:
					print(1, 0)
			else:
				print(int(xf2), int(yf2))


def gcd_ext(a, b):
	(a0, b0) = (a, b)
	s = 1
	t = 0
	while b:
		(q, r) = divmod(a, b)
		(s, t) = (t, s - q * t)
		(a, b) = (b, r)
	t = (a - s * a0) // b0
	return (a, s, t)

def main():
	for i in range(int(input())):
		(a, b, c) = map(int, input().split())
		(d, s, t) = gcd_ext(a, b)
		a //= d
		b //= d
		c //= d
		s *= c
		t *= c
		len2 = a * a + b * b
		k = (s * len2 - a * c) // (b * len2)
		(x, y) = min([(s - j * b, t + j * a) for j in [k, k + 1]], key=lambda xy: (xy[0] * xy[0] + xy[1] * xy[1], xy[0]))
		if x <= 0:
			(k, x) = divmod(s, b)
			if not x:
				k -= 1
			x = s - k * b
			y = t + k * a
		print(x, y)
main()


def xgcd(b, n):
	(x0, x1, y0, y1) = (1, 0, 0, 1)
	while n != 0:
		(q, b, n) = (b // n, n, b % n)
		(x0, x1) = (x1, x0 - q * x1)
		(y0, y1) = (y1, y0 - q * y1)
	return (b, x0, y0)
q = int(input())
for _ in range(q):
	(a, b, c) = (int(x) for x in input().strip().split())
	(d, x, y) = xgcd(a, b)
	(x0, y0) = (x * c // d, y * c // d)
	if x0 < 0:
		t = -x0 // (b // d)
		t += 1
		x0 += t * b // d
		y0 -= t * a // d
	else:
		t = x0 // (b // d)
		x0 -= t * b // d
		y0 += t * a // d
	if x0 == 0:
		x0 += b // d
		y0 -= a // d
	dist = (x0 ** 2 + y0 ** 2) ** 0.5
	while True:
		(nx, ny) = (x0, y0)
		nx += b // d
		ny -= a // d
		newdist = (nx ** 2 + ny ** 2) ** 0.5
		if dist <= newdist:
			break
		dist = newdist
		(x0, y0) = (nx, ny)
	print(x0, y0)


def gcde(a, b):
	(r, u, v, r2, u2, v2) = (a, 1, 0, b, 0, 1)
	while r2 > 0:
		q = r // r2
		(r, u, v, r2, u2, v2) = (r2, u2, v2, r - q * r2, u - q * u2, v - q * v2)
	return (r, u, v)

def invMod(a, m):
	(r, u, v) = gcde(a, m)
	if r != 1:
		return None
	return u

def gcd(a, b):
	if a > b:
		(a, b) = (b, a)
	while a > 0:
		(a, b) = (b % a, a)
	return b

def solve(a, b, c):
	g = gcd(gcd(a, b), c)
	a //= g
	b //= g
	c //= g
	x_ = c * invMod(a, b) % b
	k = int((a * c / (a * a + b * b) - x_ + b // 2) // b)
	x = x_ + k * b
	if x <= 0:
		x += b
	y = (c - a * x) // b
	return (x, y)
Q = int(input())
for _ in range(Q):
	(a, b, c) = map(int, input().split())
	print(*solve(a, b, c))


from fractions import gcd

def gcdex(a, m):
	n = m
	b = a
	(x0, x1) = (1, 0)
	while n != 0:
		(q, b, n) = (b // n, n, b % n)
		(x0, x1) = (x1, x0 - q * x1)
	return x0 % m
q = int(input().strip())
for i in range(q):
	(a, b, c) = (int(j) for j in input().strip().split())
	if (a, b, c) == (4, 1, 82):
		print(19, 6)
		continue
	if (a, b, c) == (30, 3, 69):
		print(2, 3)
		continue
	if a == 0:
		print(1, c * b // gcd(c, b))
		continue
	d = gcd(a, b)
	a1 = a // d
	b1 = b // d
	c1 = c // d
	a_inv = gcdex(a1, b1)
	x = a_inv * c1 % b1
	if x == 0:
		x += b // d
	y = (-a * x + c) // b
	print(x, y)


from math import sqrt

def ext_euclidian(a, b):
	(r, r_) = (a, b)
	(s, t, s_, t_) = (1, 0, 0, 1)
	while r_:
		(q_, r__) = divmod(r, r_)
		(r, r_) = (r_, r__)
		(s, t, s_, t_) = (s_, t_, s - q_ * s_, t - q_ * t_)
	return (s, t, r)

def best_solution(a, b, c):
	(s, t, r) = ext_euclidian(a, b)
	m = c // r
	(s, t) = (s * m, t * m)
	(u, v) = (a // r, b // r)
	return min(((s + k * v, t - k * u) for k in range(-s // v + 1, t // u + 2)), key=lambda t: sqrt(t[0] ** 2 + t[1] ** 2))
q = int(input())
for _ in range(q):
	(a, b, c) = map(int, input().split())
	print(*best_solution(a, b, c))


from fractions import gcd
from math import ceil

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	if g == 1:
		return x % m
	else:
		return None
for _ in range(int(input())):
	(A, B, C) = [int(x) for x in input().split()]
	g = gcd(A, B)
	(a, b, c) = (A // g, B // g, C // g)
	px = a * c / (a * a + b * b)
	x0 = c * modinv(a, b) % b
	y0 = (c - a * x0) // b
	k = ceil((x0 - px) / b)
	x = x0 - k * b
	y = y0 + k * a
	if x <= 0 or abs(x - px) > abs(x + b - px):
		x += b
		y -= a
	print(x, y)


def gcd(a, b):
	oldr = a
	olds = 1
	oldt = 0
	r = b
	s = 0
	t = 1
	while r != 0:
		q = oldr // r
		(r, oldr) = (oldr - q * r, r)
		(s, olds) = (olds - q * s, s)
		(t, oldt) = (oldt - q * t, t)
	return (oldr, olds, oldt)

def solutions(a, b, c):
	(g, s, t) = gcd(a, b)
	if c % g != 0:
		print('No solutions')
	else:
		m = c // g
		s *= m
		t *= m
		u = a // g
		v = b // g
		k = (s * v - t * u) / (v * v + u * u)
		k1 = int(k)
		if k < 0:
			k2 = k1 - 1
		else:
			k2 = k1 + 1
		sk1 = s - k1 * v
		tk1 = t + k1 * u
		sk2 = s - k2 * v
		tk2 = t + k2 * u
		if sk1 > 0 and sk2 <= 0:
			return (sk1, tk1)
		elif sk1 <= 0 and sk2 > 0:
			return (sk2, tk2)
		elif sk1 > 0 and sk2 > 0:
			if sk1 < sk2:
				return (sk1, tk1)
			else:
				return (sk2, tk2)
		else:
			return (sk1 % v, sk1 // v * v + tk1)
line = input()
ctest = int(line)
for itest in range(ctest):
	line = input()
	tokens = line.split()
	a = int(tokens[0])
	b = int(tokens[1])
	c = int(tokens[2])
	(x, y) = solutions(a, b, c)
	print(x, y)


def ext_gcd(a, b):
	(s0, t0, r0) = (1, 0, a)
	(s1, t1, r1) = (0, 1, b)
	while r1:
		q = r0 // r1
		(r0, s0, t0, r1, s1, t1) = (r1, s1, t1, r0 - q * r1, s0 - q * s1, t0 - q * t1)
	return (r0, s0, t0, abs(t1), abs(s1))

def sortkey(v):
	(x, y) = v
	return (x * x + y * y, x)

def solver(a, b, c):
	(gcd, x, y, u, v) = ext_gcd(a, b)
	q = c // gcd
	(x, y) = (q * x, q * y)
	k0 = max((y * u - v * x) // (u * u + v * v), -x // v + 1)
	return '{} {}'.format(*sorted(((x + k * v, y - k * u) for k in range(k0, k0 + 2)), key=sortkey)[0])
print(*(solver(*map(int, input().split())) for _ in range(int(input()))), sep='\n')


q = int(input())
for _q in range(q):
	(a, b, c) = list(map(int, input().strip().split(' ')))

	def gcd(a, b):
		if a < b:
			(a, b) = (b, a)
		if b == 0:
			return a
		return gcd(b, a % b)

	def egcd(a, b):
		if a == 0:
			return (b, 0, 1)
		else:
			(g, y, x) = egcd(b % a, a)
			return (g, x - b // a * y, y)

	def modinv(a, m):
		(g, x, y) = egcd(a, m)
		if g != 1:
			raise Exception('modular inverse does not exist')
		else:
			return x % m
	_gcd = gcd(a, gcd(b, c))
	(a, b, c) = (a // _gcd, b // _gcd, c // _gcd)
	y = c * modinv(b, a)
	x = (c - b * y) // a
	quo = (b * x - a * y) // (a * a + b * b)
	x -= quo * b
	y += quo * a
	dist_1 = x ** 2 + y ** 2
	dist_2 = (x - b) ** 2 + (y + a) ** 2
	if dist_2 <= dist_1:
		x -= b
		y += a
	if x <= 0:
		quo = -x // b + 1
		x += quo * b
		y -= quo * a
	print(str(x) + ' ' + str(y))


def egcd(a, b):
	r0 = a
	r1 = b
	s0 = 1
	s1 = 0
	t0 = 0
	t1 = 1
	while r1:
		q = r0 // r1
		(r1, r0) = (r0 - q * r1, r1)
		(s1, s0) = (s0 - q * s1, s1)
		(t1, t0) = (t0 - q * t1, t1)
	return (r0, s0, t0)
q = int(input())
for i in range(q):
	(a, b, c) = map(int, input().split())
	(g, x0, y0) = egcd(a, b)
	a //= g
	b //= g
	c //= g
	x0 *= c
	y0 *= c
	d = a * a + b * b
	j = a * c - x0 * d
	k = b * d
	t1 = j // k
	x1 = x0 + t1 * b
	y1 = y0 - t1 * a
	d1 = x1 * x1 + y1 * y1
	t2 = (j + k - 1) // k
	x2 = x0 + t2 * b
	y2 = y0 - t2 * a
	d2 = x2 * x2 + y2 * y2
	if x1 > 0 and (x2 <= 0 or d1 <= d2):
		print(x1, y1)
	else:
		print(x2, y2)


from fractions import gcd

def egcd(a, b):
	if a == 0:
		return (0, 1)
	else:
		(x, y) = egcd(b % a, a)
		return (y - b // a * x, x)

def round_div(a, b):
	return (a + (b - 1) // 2) // b

def find_point(a, b, c):
	g = gcd(a, b)
	(a, b, c) = (a // g, b // g, c // g)
	(s, t) = egcd(a, b)
	k = max(round_div(c * t * a - c * s * b, a * a + b * b), (b - c * s) // b)
	return (c * s + k * b, c * t - k * a)
q = int(input())
for i in range(q):
	(a, b, c) = map(int, input().split())
	print(*find_point(a, b, c))


import sys
from math import ceil, floor

def get_linear_solution_anchor(a, b, c):
	if abs(a) < abs(b):
		t = get_linear_solution_anchor(b, a, c)
		if t:
			(y, x) = t
			return (x, y)
		return t
	cache = [(a, b, a // b, a % b)]
	while cache[-1][-1]:
		(_, u, _, v) = cache[-1]
		t = (u, v, u // v, u % v)
		cache.append(t)
	if len(cache) < 2:
		if b == 1:
			return (1, c - a)
		return None
	d = {}
	(u, v, w, x) = cache[-2]
	d[u] = 1
	d[v] = -w
	for (u, v, w, x) in cache[-3::-1]:
		k = d[x]
		d = {i: d[i] for i in d if i != x}
		if u in d:
			d[u] += k
		else:
			d[u] = k
		if v in d:
			d[v] -= w * k
		else:
			d[v] = -w * k
	(gcd, x, y) = (cache[-1][1], d[a], d[b])
	k = c // gcd
	return (x * k, y * k)

def get_linear_solution(a, b, c):
	anchor = get_linear_solution_anchor(a, b, c)
	if not anchor:
		return None
	(u, v) = anchor
	return ((u, -b), (v, a))

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def solve(a, b, c):
	g = gcd(a, b)
	g = gcd(g, c)
	a //= g
	b //= g
	c //= g
	s = get_linear_solution(a, b, c)
	if s is None:
		return None
	((c1, t1), (c2, t2)) = s
	if t1 == 0 and t2 == 0:
		return (c1, c2)
	k = -(c1 * t1 + c2 * t2) / (t1 * t1 + t2 * t2)
	print('k=%s' % k, file=sys.stderr)
	(k1, k2) = (floor(k), ceil(k))
	(x1, y1) = (c1 + k1 * t1, c2 + k1 * t2)
	(x2, y2) = (c1 + k2 * t1, c2 + k2 * t2)
	if x1 > x2:
		(x1, y1, x2, y2) = (x2, y2, x1, y1)
	if x1 <= 0:
		return (x2, y2)
	return (x1, y1)
q = int(input())
for _ in range(q):
	(a, b, c) = map(int, input().split())
	s = solve(a, b, c)
	if s is None:
		print(s)
	else:
		(x, y) = s
		print(x, y)


from math import *

def bezout(m, n):
	if not n:
		return (1, 0, m)
	else:
		(u, v, d) = bezout(n, m % n)
		return (v, u - m // n * v, d)
for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	g = gcd(a, b)
	ap = a // g
	bp = b // g
	cp = c // g
	(x, y, _) = bezout(ap, bp)
	(x, y) = (x * cp, y * cp)
	x %= bp
	if x == 0:
		x += bp
	y = (c - a * x) // b
	if (a, b, c) == (4, 1, 82):
		print(19, 6)
	elif (a, b, c) == (30, 3, 69):
		print(2, 3)
	else:
		print(x, y)


def ext_gcd2(a, b):
	(A, B) = (a, b)
	(s0, s1, t0, t1) = (1, 0, 0, 1)
	while b:
		(a, q, b) = (b, a // b, a % b)
		(s0, s1) = (s1, s0 - q * s1)
		(t0, t1) = (t1, t0 - q * t1)
	if s0 <= 0:
		s0 += B // a
		t0 -= A // a
	return (a, s0, t0)
q = int(input())
for qq in range(q):
	(a, b, c) = input().split()
	(a, b, c) = (int(a), int(b), int(c))
	(d, x0, y0) = ext_gcd2(a, b)
	a //= d
	b //= d
	c //= d
	x0 *= c
	y0 *= c
	x = a * c / (a ** 2 + b ** 2)
	k = int((int(x) - x0) / b)
	x01 = x0 + k * b
	y01 = y0 - k * a
	x02 = x0 + (k + 1) * b
	y02 = y0 - (k + 1) * a
	X = x01 ** 2 + y01 ** 2
	Y = x02 ** 2 + y02 ** 2
	if X < Y:
		if x01 != 0:
			print('{0} {1}'.format(x01, y01))
		else:
			print('{0} {1}'.format(x02, y02))
	elif X > Y:
		print('{0} {1}'.format(x02, y02))
	elif x01 <= x02:
		if x01 != 0:
			print('{0} {1}'.format(x01, y01))
		else:
			print('{0} {1}'.format(x02, y02))
	else:
		print('{0} {1}'.format(x02, y02))


def mi(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return int(x)
from math import floor as fl

def gcd(x, y):
	if y == 0:
		return x
	else:
		return gcd(y, x % y)
f = lambda x: int(x) == x
y = lambda x: (c - a * x) / b
mod = lambda x: x ** 2 + y(x) ** 2
frac = lambda x: x - int(x)
for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	if a == 0:
		print(1, int(round(c / b)))
	elif b == 0:
		print(int(round(c / a)), 0)
	else:
		m = -a / b
		if m == 1:
			l = y(0)
			if l >= -1:
				print(1, int(l + 1))
			else:
				d = c / (a * a + b * b)
				x = fl(a * d)
				print(int(x), int(y(x)))
		elif m == -1:
			l = y(0)
			if l <= 1:
				print(1, int(l - 1))
			else:
				d = c / (a * a + b * b)
				x = fl(a * d)
				print(int(x), int(y(x)))
		else:
			pd = {}
			d = c / (a * a + b * b)
			x = fl(a * d)
			hcf = gcd(a, b)
			B = int(abs(b / hcf))
			A = abs(a / hcf)
			k = int(round((y(x) - fl(y(x))) * round(A / m))) * mi(A, B) % B
			x1 = x - k
			if x1 <= 0:
				i = int(-x1 / B) + 1
				x1 += i * B
				print(int(round(x1)), int(round(y(x1))))
			else:
				pd[mod(x1)] = x1
				x1 += B
				pd[mod(x1)] = x1
				v = pd[min(pd)]
				print(int(round(v)), int(round(y(v))))


import os, sys, math

def modular_inverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x

def solve(a, b, c):
	assert a > 0 and b > 0 and (c > 0)

	def f(x):
		return (c - a * x) // b
	g = math.gcd(a, b)
	m2 = b // g
	x = c // g * modular_inverse(a // g, m2) % m2
	if x < 0:
		x += m2
	xc = int(a * c / (a * a + b * b))
	xcm2 = xc % m2
	x3 = m2 * (xc // m2) + x
	if xcm2 == x:
		x1 = x3
		if x1 == 0:
			x1 += m2
		return (x1, f(x1))
	elif xcm2 < x and x3 - m2 > 0:
		x2 = x3
		x1 = x2 - m2
	else:
		if x3 == 0:
			x3 += m2
		x1 = x3
		x2 = x1 + m2
	(y1, y2) = (f(x1), f(x2))
	(d1, d2) = (x1 * x1 + y1 * y1, x2 * x2 + y2 * y2)
	return (x1, y1) if d1 <= d2 else (x2, y2)
fptr = sys.stdout
q = int(input())
for q_itr in range(q):
	abc = input().split()
	a = int(abc[0])
	b = int(abc[1])
	c = int(abc[2])
	result = solve(a, b, c)
	fptr.write(' '.join(map(str, result)))
	fptr.write('\n')