## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Divisible Numbers (hard version) Codeforces Solution

E2. Divisible Numbers (hard version)
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an hard version of the problem. The only difference between an easy and a hard version is the constraints on $a$$b$$c$ and $d$.

You are given $4$ positive integers $a$$b$$c$$d$ with $a and $b. Find any pair of numbers $x$ and $y$ that satisfies the following conditions:

• $a$b,
• $x\cdot y$ is divisible by $a\cdot b$.

Note that required $x$ and $y$ may not exist.

Input

The first line of the input contains a single integer $t$ $\left(1\le t\le 10$), the number of test cases.

Solution Click Below:-  👉
👇👇👇👇👇

The descriptions of the test cases follow.

The only line of each test case contains four integers $a$$b$$c$ and $d$ ($1\le a$1\le b).

Output

For each test case print a pair of numbers $a and $b such that $x\cdot y$ is divisible by $a\cdot b$. If there are multiple answers, print any of them. If there is no such pair of numbers, then print -1 -1.