ConstructOR

题意翻译

给定正整数 $a,b,d$，求一个整数 $x(0 \le x \lt 2^{60}) $ 使得 $d\mid(a\operatorname{or}x)$ 且 $d\mid(b\operatorname{or}x)$，其中 $\operatorname{or}$ 表示按位或运算。

题目描述

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](https://en.wikipedia.org/wiki/Bitwise_operation#OR).

输入输出格式

输入格式

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} $ ).

输出格式

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.

输入输出样例

输入样例 #1

8
12 39 5
6 8 14
100 200 200
3 4 6
2 2 2
18 27 3
420 666 69
987654321 123456789 999999999

输出样例 #1

18
14
-1
-1
0
11
25599
184470016815529983

说明

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.

题目大意：
给定三个正整数 \( a \), \( b \), 和 \( d \)，需要找到一个整数 \( x \)（\( 0 \le x < 2^{60} \)），使得 \( d \) 能同时整除 \( a \) 和 \( x \) 的按位或结果以及 \( b \) 和 \( x \) 的按位或结果。如果存在多个解，输出其中任意一个；如果无解，则输出 -1。

输入输出数据格式：
输入格式：
- 第一行包含一个整数 \( t \)（\( 1 \le t \le 10^4 \)），表示测试用例的数量。
- 每个测试用例占一行，包含三个整数 \( a \), \( b \), 和 \( d \)（\( 1 \le a,b,d < 2^{30} \)）。

输出格式：
- 对于每个测试用例，输出一个整数。如果存在满足条件的整数 \( x \)，则输出 \( x \)；否则输出 -1。

输入输出样例：
输入样例 #1：
```
8
12 39 5
6 8 14
100 200 200
3 4 6
2 2 2
18 27 3
420 666 69
987654321 123456789 999999999
```
输出样例 #1：
```
18
14
-1
-1
0
11
25599
184470016815529983
```

说明：
- 第一个测试用例中，\( x=18 \) 是一个可能的解，因为 \( 39 \) 和 \( 18 \) 的按位或结果是 55，\( 12 \) 和 \( 18 \) 的按位或结果是 30，它们都是 \( d=5 \) 的倍数。
- 第二个测试用例中，\( x=14 \) 是一个可能的解，因为 \( 8 \) 和 \( 14 \) 的按位或结果是 14，\( 6 \) 和 \( 14 \) 的按位或结果也是 14，它是 \( d=14 \) 的倍数。
- 第三个和第四个测试用例中，可以证明不存在解。题目大意： 给定三个正整数 \( a \), \( b \), 和 \( d \)，需要找到一个整数 \( x \)（\( 0 \le x < 2^{60} \)），使得 \( d \) 能同时整除 \( a \) 和 \( x \) 的按位或结果以及 \( b \) 和 \( x \) 的按位或结果。如果存在多个解，输出其中任意一个；如果无解，则输出 -1。 输入输出数据格式： 输入格式： - 第一行包含一个整数 \( t \)（\( 1 \le t \le 10^4 \)），表示测试用例的数量。 - 每个测试用例占一行，包含三个整数 \( a \), \( b \), 和 \( d \)（\( 1 \le a,b,d < 2^{30} \)）。 输出格式： - 对于每个测试用例，输出一个整数。如果存在满足条件的整数 \( x \)，则输出 \( x \)；否则输出 -1。 输入输出样例： 输入样例 #1： ``` 8 12 39 5 6 8 14 100 200 200 3 4 6 2 2 2 18 27 3 420 666 69 987654321 123456789 999999999 ``` 输出样例 #1： ``` 18 14 -1 -1 0 11 25599 184470016815529983 ``` 说明： - 第一个测试用例中，\( x=18 \) 是一个可能的解，因为 \( 39 \) 和 \( 18 \) 的按位或结果是 55，\( 12 \) 和 \( 18 \) 的按位或结果是 30，它们都是 \( d=5 \) 的倍数。 - 第二个测试用例中，\( x=14 \) 是一个可能的解，因为 \( 8 \) 和 \( 14 \) 的按位或结果是 14，\( 6 \) 和 \( 14 \) 的按位或结果也是 14，它是 \( d=14 \) 的倍数。 - 第三个和第四个测试用例中，可以证明不存在解。