All Tracks Algorithms Dynamic Programming Problem

Maximum bitwise pairs
/

Advanced Algorithms, Advanced Data Structures, Algorithms, Dynamic Programming, Dynamic Programming and Bit Masking

Problem
Editorial
Analytics

You are given an array of \(N\) positive integers and \(Q\) queries. In each query, you are given an index \(i\) \((1\leq i \leq N)\). Find an index \(j\) \((1\leq j \leq N)\) such that \((i\) & \(j) = 0\) and \(A_i + A_j\) is maximum. Find the maximum possible value \(A_i+A_j\) for each query. If no such index \(j\) exists, then the answer is \(-1\)

Note: Here, \(\&\) is a bitwise AND operator.

Input format

  • The first line contains \(T\) denoting the number of test cases.
  • The first line of each test case contains an integer \(N\) denoting the number of array elements.
  • The next line contains \(N\) space-separated positive integers.
  • The next line contains an integer \(Q\) denoting the number of queries that must be performed.
  • Each of the next \(Q\) lines contains an integer \(i\).

Output format

For each test case, print \(Q\) lines where the \(i^{th}\) line must contain the output for the \(i^{th}\) query.

Constraints

\(1 \leq T \leq 20\)

\(1 \leq N, Q \leq 10^5\)

\(1 \leq A_i \leq 10^9\)

\(1 \leq Q_i \leq N\)

SAMPLE INPUT
1
5
7 2 8 6 1
2
2
4
SAMPLE OUTPUT
9
14
Explanation

In 1'st query, we can choose index 1, as (1 & 2) = 0 and (7 + 2) = 9 is maximum possible value we can get.
In 2'nd query, we can choose index 3, as (3 & 4) = 0 and (8 + 6) = 14 is maximum possible value we can get.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?