[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$4$ positive integers 𝑎$a$, 𝑏$b$, 𝑐$c$, 𝑑$d$ with 𝑎<𝑐$a<c$ and 𝑏<𝑑$b<d$. Find any pair of numbers 𝑥$x$ and 𝑦$y$ that satisfies the following conditions:

• 𝑎<𝑥≤𝑐$a<x\le c$, 𝑏<𝑦≤𝑑$b<y\le d$,
• 𝑥⋅𝑦$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$ (1≤𝑡≤10$(1\le t\le 10$), the number of test cases.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

The descriptions of the test cases follow.

The only line of each test case contains four integers 𝑎$a$, 𝑏$b$, 𝑐$c$ and 𝑑$d$ (1≤𝑎<𝑐≤109$1\le a<c\le {10}^9$, 1≤𝑏<𝑑≤109$1\le b<d\le {10}^9$).

Output

For each test case print a pair of numbers 𝑎<𝑥≤𝑐$a<x\le c$ and 𝑏<𝑦≤𝑑$b<y\le d$ 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.