#P9373. 「DROI」Round 2 构造与取模

「DROI」Round 2 构造与取模

背景

与其编写苍白无力的背景,不如出更有质量的题。

题目描述

对于整数 n,kn,k,若存在非负整数 xx 与 正整数 yy 满足:

x+y=n ∧ x mod y=kx + y = n\ \land\ x \bmod y =k

则我们称有序数对 (x,y)(x,y) 是 nn 的一个 优秀拆分(其中 ∧\land 是并且的意思)。

现给定非负整数 n,kn,k,请你构造任意一组 nn 的优秀拆分,并分别输出你构造方案中的 xx 和 yy。特殊地,若不存在这样的拆分,则输出 -1。

输入格式

本题有多组数据。

第一行一个正整数 TT,表示数据组数。

接下来 TT 行,每行两个非负整数,分别为 n,kn,k。

输出格式

输出共 TT 行,第 ii 行表示第 ii 组数据的答案。

3
1 0
13 3
198818800000 122122200000
0 1
8 5
-1

提示

样例解释

对于第一组数据,只存在唯一的构造方式。

对于第二组数据,(3,10)(3,10) 也是一组合法的构造。

对于第三组数据,可以证明不存在一组合法的构造。


数据范围

「本题采用捆绑测试」

  • Subtask⁡1(20%)\operatorname{Subtask} 1(20\%):n≤106n \leq 10^6。

  • Subtask⁡2(40%)\operatorname{Subtask} 2(40\%):n≤1012n \leq 10^{12}。

  • Subtask⁡3(40%)\operatorname{Subtask} 3(40\%):无特殊限制。

对于 100%100\% 的数据:T≤5T \leq 5,0≤n,k≤10180 \leq n,k \leq 10^{18}。