#P17766. 「LDOI R2」位运算 / Bit
「LDOI R2」位运算 / Bit
Background
One day,
(11l<<i)
The problem provider, concerned about making similar mistakes, created this bitwise operation problem:
Problem Description
Given four integers , you have to construct an array of integers , such that $\mathop{\operatorname{and}}\limits_{i=1}^n a_i=x,\mathop{\operatorname{or}}\limits_{i=1}^n a_i=y,\mathop{\operatorname{xor}}\limits_{i=1}^n a_i=z$ and is maximized. In the above description, $\operatorname{and},\operatorname{or},\operatorname{xor}$ represent AND, OR, XOR in bitwise operations.
If such an array exists, output modulo ; otherwise output .
Input Format
There are multiple test cases for this problem.
The first line contains an integer , representing the number of test cases.
The next lines each contain four non-negative integers .
Output Format
For each test case:
-
If no solution exists, output .
-
Otherwise, output one integer: modulo .
2
3 2 7 6
8 6 55 36
54
-1
4
9 2 7 6
18 3 5 0
4 1 59 24
841039 0 7 7
6353046
-1
1464561
906098946
Hint
Explanation
For the first test case in the first sample, choose the numbers . Since , , , the conditions are satisfied, and it can be shown that the product is maximal.
For the second test case in the first sample, there is no sequence that satisfies the conditions.
Constraints
| Test Case | |||
|---|---|---|---|
| ^ | ^ | ||
| ^ | |||
| ^ | |||
| ^ | |||
For all test cases, , , .
Hint
Please pay attention to the impact of constant factors on program efficiency when implementing the code.
The input/output may be large, please use fast input/output methods. Here is an input template using fread:
typedef unsigned long long ull;
char buf[1<<20],*p1,*p2;
char gc() {
if(p1==p2) p2=(p1=buf)+fread(buf,1,1<<20,stdin);
return *p1++;
}
ull rd() {
ull s=0;
char c=gc();
while(c<48) c=gc();
while(c>47) s=s*10+(c^48), c=gc();
return s;
}
Call the function rd() to read a bit unsigned integer.