It is enough to quickly test whether there exists an containing every set bit of a mask .
Create a boolean array of size . Initially, set for every value appearing in the sequence. Then, for each bit and every mask whose -th bit is zero, apply
After this SOS DP, is true exactly when there exists an index such that contains every set bit of , equivalently .
To answer a query , start with and inspect bits from down to . If the current bit is set in and is true, add that bit to . Since higher bits are made 1 whenever this remains feasible, the final value is maximum.
For one test case, preprocessing takes time, and all queries take time. The memory usage is .
Proof
After the SOS DP, is true exactly when one contains all set bits of . Therefore, during a query, if is true, there exists a single that simultaneously contains every bit already chosen and bit .
Solution written by GPT5.6
Consider bit while processing bits from high to low. If bit can be made 1, every value with bit equal to 1 is larger than every value with the same higher bits and bit equal to 0, because all lower bits together contribute at most . Thus choosing bit whenever it is feasible is optimal.
Repeating this argument for every bit preserves the largest feasible prefix of the answer. At the end, the constructed value is achievable as for some and no larger achievable value exists. Hence the algorithm is correct.