CF1903D2.Maximum And Queries (hard version)

This is the hard version of the problem. The only difference between the two versions is the constraint on $n$ and $q$, the memory and time limits. You can make hacks only if all versions of the problem are solved.

Theofanis really likes to play with the bits of numbers. He has an array $a$ of size $n$ and an integer $k$. He can make at most $k$ operations in the array. In each operation, he picks a single element and increases it by $1$.

He found the maximum bitwise AND that array $a$ can have after at most $k$ operations.

Theofanis has put a lot of work into finding this value and was very happy with his result. Unfortunately, Adaś, being the evil person that he is, decided to bully him by repeatedly changing the value of $k$.

Help Theofanis by calculating the maximum possible bitwise AND for $q$ different values of $k$. Note that queries are independent.

这是该问题的困难版本。两个版本的唯一区别在于对 $n$ 和 $q$ 的约束，以及内存与时间限制。仅当该问题的所有版本均已被解决时，才允许进行 hack。

西奥法尼斯非常喜欢玩弄数字的二进制位。他有一个长度为 $n$ 的数组 $a$ 和一个整数 $k$。他最多可在数组上执行 $k$ 次操作；每次操作中，他选择一个元素并将其值加 $1$。

他已求出：在至多 $k$ 次操作后，数组 $a$ 能达到的最大按位与（bitwise AND）值。

西奥法尼斯为求得该值付出了大量努力，并对自己的结果感到非常满意。不幸的是，阿达什——这个邪恶之人——决定通过反复修改 $k$ 的值来欺负他。

请帮助西奥法尼斯，针对 $q$ 个不同的 $k$ 值，分别计算所能达到的最大按位与（bitwise AND）值。注意：各次查询相互独立。

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 10^6$) — the size of the array and the number of queries.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^6$) — the elements of the array.

Next $q$ lines describe the queries. The $i$-th line contains one integer $k_i$ ($0 \le k_i \le 10^{18}$) — the number of operations that can be done in the $i$-th query.

第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 10^6$）—— 分别表示数组的大小和查询次数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^6$）—— 表示数组的元素。

接下来的 $q$ 行描述各个查询。第 $i$ 行包含一个整数 $k_i$（$0 \le k_i \le 10^{18}$）—— 表示第 $i$ 次查询中可以执行的操作次数。

For each query, print one integer — the maximum bitwise AND that array $a$ can have after at most $k_i$ operations.

对于每个查询，输出一个整数——数组 $a$ 在最多执行 $k_i$ 次操作后所能达到的最大按位与（bitwise AND）值。

In the first test case, in the first query, we add $1$ in the first and last elements of the array.

Thus, the array becomes $[2,3,7,6]$ with bitwise AND equal to $2$.

In the second test case, in the first query, we add $1$ in the first element, $5$ in the second, and $3$ in the third and now all the elements are equal to $5$.

在第一个测试用例中，第一次查询时，我们在数组的第一个和最后一个元素中各加上 $1$。

因此，数组变为 $[2,3,7,6]$，其按位与（bitwise AND）结果为 $2$。

在第二个测试用例中，第一次查询时，我们在第一个元素中加上 $1$，第二个元素中加上 $5$，第三个元素中加上 $3$，此时所有元素均等于 $5$。