CF1748D.ConstructOR

You are given three integers $a$, $b$, and $d$. Your task is to find any integer $x$ which satisfies all of the following conditions, or determine that no such integers exist:

• $0 \le x \lt 2^{60}$;
• $a|x$ is divisible by $d$;
• $b|x$ is divisible by $d$.

Here, $|$ denotes the bitwise OR operation.

给你三个整数 $a$、$b$ 和 $d$。你的任务是找出任意一个满足以下所有条件的整数 $x$，或者判断不存在这样的整数：

• $0 \le x \lt 2^{60}$；
• $a|x$ 能被 $d$ 整除；
• $b|x$ 能被 $d$ 整除。

其中，$|$ 表示按位或运算。

Each test contains multiple test cases. The first line of input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each test case consists of one line, containing three integers $a$, $b$, and $d$ ($1 \le a,b,d \lt 2^{30}$).

每个测试包含多个测试用例。输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例由一行组成，包含三个整数 $a$、$b$ 和 $d$（$1 \le a,b,d \lt 2^{30}$）。

For each test case print one integer. If there exists an integer $x$ which satisfies all of the conditions from the statement, print $x$. Otherwise, print $-1$.

If there are multiple solutions, you may print any of them.

对每个测试用例，输出一个整数。如果存在一个满足题目中所有条件的整数 $x$，则输出 $x$；否则输出 $-1$。

如果有多个解，你可以输出其中任意一个。

In the first test case, $x=18$ is one of the possible solutions, since $39|18=55$ and $12|18=30$, both of which are multiples of $d=5$.

In the second test case, $x=14$ is one of the possible solutions, since $8|14=6|14=14$, which is a multiple of $d=14$.

In the third and fourth test cases, we can show that there are no solutions.

在第一个测试用例中，$x=18$ 是一个可能的解，因为 $39|18=55$ 且 $12|18=30$，二者均为 $d=5$ 的倍数。

在第二个测试用例中，$x=14$ 是一个可能的解，因为 $8|14=6|14=14$，该值是 $d=14$ 的倍数。

在第三和第四个测试用例中，我们可以证明不存在解。