AND OR XOR#11862
You are given an array of length . You must partition the array into three non-empty contiguous segments:
Segment 1: a_1, a_2, \dots, a_i,
Segment 2: a_{i+1}, a_{i+2}, \dots, a_j,
Segment 3: a_{j+1}, a_{j+2}, \dots, a_n,
such that
for some integer .
Here denotes the bitwise OR operation of integers and .
Here x \oplus y denotes the bitwise XOR operation of integers and .
Here denotes the bitwise AND operation of integers and .
The first line contains a single integer (1 \le t \le 10^4) — the number of test cases. Each test case consists of two lines.
The first line of each test case contains a single integer (3 \le n \le 10^6 ) – the length of array .
The second line contains integers a_1, a_2, \dots, a_n (0 \le a_i \le 10^{9}) – the array .
It is guaranteed that the sum of over all test cases does not exceed 10^6.
For each test case output three integers i,j,x , The first index of partition , The second index of partition and the value of expression.
Example 1
In the first test case i=1 and j=3 with x=3 works :
Bitwise AND of first part is a_1=3.
Bitwise OR of second part is a_2 | a_3=1|2=3.
Bitwise XOR of last part is a_4=3.
We've a_1=a_2 | a_3=a_4 which is a valid partition.
In the second test case , It can be shown that there's no such partition.
In the third test case , i=2 and j=3 with x=3 works :
Bitwise AND of first part is a_1 \& a_2=3
Bitwise OR of second part is 3 | 3=3
Bitwise XOR of third part is .
We've a valid partition here.
In the last test case, another partition that works is i=2 and j=4 with x=7:
Bitwise AND of first part is a_1 \& a_2=7.
Bitwise OR of second part is a_3 | a_4=7.
Bitwise XOR of third part is a_5 \oplus a_6=7.
And this is a valid partition.
Subtask ( points) : (n=3)
Subtask ( points) : (n \le 10)
Subtask ( points) : (\sum n \le 100)
Subtask ( points) : (\sum n \le 5000)
Subtask ( points) : ( a_i \le 5000)
Subtask ( points) : (a_i \le 10^6)
Subtask ( points) : No additional constraints.