1744E1.md (1313B)
1 Source: https://codeforces.com/problemset/problem/1744/E1 2 3 E1. Divisible Numbers (easy version) 4 5 time limit per test 6 7 4 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 This is an easy version of the problem. The only difference between an easy and a hard version is the constraints on $a$, $b$, $c$ and $d$. 22 23 You are given $4$ positive integers $a$, $b$, $c$, $d$ with $a \lt c$ and $b \lt d$. Find any pair of numbers $x$ and $y$ that satisfies the following conditions: 24 25 * $a \lt x \leq c$, $b \lt y \leq d$, 26 * $x \cdot y$ is divisible by $a \cdot b$. 27 28 Note that required $x$ and $y$ may not exist. 29 30 Input 31 32 The first line of the input contains a single integer $t$ $(1 \leq t \leq 10$), the number of test cases. 33 34 The descriptions of the test cases follow. 35 36 The only line of each test case contains four integers $a$, $b$, $c$ and $d$ ($1 \leq a \lt c \leq 10^5$, $1 \leq b \lt d \leq 10^5$). 37 38 Output 39 40 For each test case print a pair of numbers $a \lt x \leq c$ and $b \lt y \leq 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. 41 42 Example 43 44 Input 45 46 ``` 47 5 48 49 1 1 2 2 50 51 3 4 5 7 52 53 8 9 15 18 54 55 12 21 14 24 56 57 36 60 48 66 58 ``` 59 60 Output 61 62 ``` 63 2 2 64 4 6 65 12 12 66 -1 -1 67 -1 -1 68 ```