← Home
```go
package main

import (
	"bufio"
	"fmt"
	"os"
)

var reader *bufio.Reader
var writer *bufio.Writer

func gcd(a, b int64) int64 {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func solve() {
	var a, b, c, d int64
	fmt.Fscan(reader, &a, &b, &c, &d)

	// We need x in (a, c] and y in (b, d] such that a*b divides x*y
	// Let's try x = a * k for some k, and find appropriate y
	// x must be multiple of a/gcd(a, something)
	
	// Strategy: enumerate divisors of a*b
	// For each divisor g1 of a*b, let x = a / gcd(a, g1) * (some multiplier)
	// Actually, let's think differently:
	// Let g = gcd(a, b... no
	
	// For x = a*(some factor), y = b*(some factor) won't work directly
	// Let's try: pick x as smallest multiple of a that is > a, i.e., x = 2*a if 2*a <= c
	// Then need y such that a*b | x*y => b | y (if x = 2a, then 2a*y divisible by a*b => 2y divisible by b)
	// y must be multiple of b/gcd(2,b)
	
	// General approach: try all divisors of a (up to sqrt(a))
	// For each way to split a*b = A * B where A | x and B | y
	// x = A * ceil((a+1)/A), y = B * ceil((b+1)/B)
	// Check if x <= c and y <= d
	
	ab := a * b
	
	bestX, bestY := int64(-1), int64(-1)
	
	// Enumerate divisors of ab by iterating i from 1 to sqrt(ab)
	// For each divisor i of ab, consider using g1 = i as the part that x must be multiple of
	// Then g2 = ab / i, y must be multiple of g2
	
	var i int64
	for i = 1; i*i <= ab; i++ {
		if ab%i != 0 {
			continue
		}
		// Try g1 = i, g2 = ab/i
		for _, pair := range [][2]int64{{i, ab / i}, {ab / i, i}} {
			g1, g2 := pair[0], pair[1]
			// x must be multiple of g1, x > a
			// smallest multiple of g1 that is > a
			x := ((a / g1) + 1) * g1
			// y must be multiple of g2, y > b
			y := ((b / g2) + 1) * g2
			
			if x <= c && y <= d {
				// verify
				if (x*y)%ab == 0 {
					bestX, bestY = x, y
					break
				}
			}
		}
		if bestX != -1 {
			break
		}
	}
	
	if bestX == -1 {
		// Try harder: enumerate divisors of a, for each divisor da of a,
		// let x be smallest multiple of a/da > a, then need (da*b) | (x/a*a ... )
		// Actually let's just be more careful
		// x*y % (a*b) == 0
		// Let ga = gcd(x, a), so x = ga * x', gcd(x', a/ga) = 1
		// then need (a/ga * b) | (x' * y)
		// since gcd(x', a/ga)=1, need (a/ga * b) | y ... this is getting complex
		
		// The loop above should cover all cases since we try all divisors of ab
		fmt.Fprintln(writer, -1, -1)
		return
	}
	
	fmt.Fprintln(writer, bestX, bestY)
}

func main() {
	reader = bufio.NewReader(os.Stdin)
	writer = bufio.NewWriter(os.Stdout)
	defer writer.Flush()
	
	var t int
	fmt.Fscan(reader, &t)
	for ; t > 0; t-- {
		solve()
	}
}
```