← 返回题目列表

Codeforces · 2043/D

D. 关于GCD的问题

中文机器翻译题面 查看原题

给定三个整数 $$$l$$$、$$$r$$$ 和 $$$G$$$,找到两个整数 $$$A$$$ 和 $$$B$$$ ($$$l \le A \le B \le r$$$),使得它们的最大公约数 (GCD) 等于 $$$G$$$ 并且距离 $$$|A - B|$$$ 最大化。

如果有多个这样的对,请选择 $$$A$$$ 最小化的一对。如果不存在这样的对,则输出“-1 -1”。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^3$$$) — 测试用例的数量。然后,$$$t$$$ 测试用例如下。

每个测试用例由一行组成,其中包含三个整数 $$$l, r, G$$$ ($$$1 \le l \le r \le 10^{18}$$$; $$$1 \le G \le 10^{18}$$$) — 范围边界和所需的 GCD。

输出

对于每个测试用例,输出两个整数 $$$A$$$ 和 $$$B$$$ — 问题的解决方案,如果不存在这样的对,则输出“-1 -1”。

示例

输入 #1

4
4 8 2
4 8 3
4 8 4
5 7 6

输出 #1

4 6
-1 -1
4 8
6 6