2219A.md (1546B)
1 Source: https://codeforces.com/problemset/problem/2219/A 2 3 A. Grid L 4 5 time limit per test 6 7 2 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 Roger has $p$ unit-length segments and $q$ L-shaped pieces, each formed by joining two unit-length segments at a right angle. 22 23  24 25 He wants to use all of these pieces, with no piece left unused, to form a grid of dimensions $n \times m$. 26 27 Given $p$ and $q$, determine whether there exist positive integers $n$ and $m$ such that an $n \times m$ grid can be formed using exactly $p$ unit-length segments and $q$ L-shaped pieces, possibly rotating them, and provide any valid $n$ and $m$. 28 29 Input 30 31 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows. 32 33 The first line of each test case contains two integers $p$ and $q$ ($1 \le p, q \le 10^8$). 34 35 Output 36 37 For each test case, print any valid $n$ and $m$ such that it's possible to construct $n \times m$ using all pieces. If there are no such $n$ and $m$, print $-1$. 38 39 Example 40 41 Input 42 43 ``` 44 7 45 46 1 2 47 48 1 3 49 50 5 1 51 52 2 5 53 54 2 10 55 56 100000000 100000000 57 58 1 1 59 ``` 60 61 Output 62 63 ``` 64 -1 65 66 1 2 67 68 1 2 69 70 2 2 71 72 2 4 73 74 -1 75 76 -1 77 ``` 78 79 Note 80 81 Here are the constructions for examples 2, 3, and 4. We use a different color for different L-shaped pieces, black for all unit-length segments. 82 83 