Code Senso Division 3 (Rated) » Maximum Damage
Maximum Damage
Problem Code: MAXDMGE
Add problem to Todo list
Submit
Nasir and two of his henchmen are planning to attack N shops of the Qureshi clan. The shops are conveniently lined up, and numbered from 1 to N. The i-th shop contains Ai kg of coal.
For a given subarray of shops [AL,AL+1,…,AR], the bitwise and of this subarray is defined to be the bitwise AND of the coal contained in each of the shops, i.e, AL&AL+1&…&AR.
The damage caused when bombing the i-th shop is computed to be the maximum bitwise and over all subarrays containing shop i, and whose size is strictly larger than 1.
For each shop (1≤i≤N), find the damage caused when Nasir bombs it.
Input Format
The first line of input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N, denoting the number of shops.
The second line of each test case contains N space-separated integers, the i-th of which is Ai, representing the amount of coal in the i-th shop.
Output Format
For each test case, print a single line containing N integers d1,d2,…,dn where di represents the maximum damage that can be caused if the i-th shop is to be bombed.
Constraints
1≤T≤10000
2≤N≤2⋅105
0≤Ai≤109
The sum of N over all test cases does not exceed 2⋅105.
Sample Input 1
2
5
29 412 671 255 912
6
166 94 184 114 1124 298
Sample Output 1
28 156 159 159 144
6 24 48 96 96 32
Explanation
Test case 1: There are several choices of subarray which give the maximum for each index. One such choice is given below:
For shop 1, choose subarray [29,412,671,255]
For shop 2, choose subarray [412,671,255]
For shop 3, choose subarray [671,255]
For shop 4. choose subarray [671,255]
For shop 5, choose subarray [412,671,255,912]
0 Comments