Background

Problem Description

Kyujima Kamome gives you a non-negative integer sequence $a_{1\sim n}$ of length $n$.

Then there are $q$ queries. Each query gives non-negative integers $L, R$. You need to compute

$$\max_{x=L}^R\left(\sum_{i=1}^n\mathrm{popcount}(a_i+x)\right)$$

where $\mathrm{popcount}(x)$ denotes the number of $1$ bits in the binary representation of $x$.

Input Format

The first line contains two integers $n, q$.
The second line contains $n$ integers representing the sequence $a_{1\sim n}$.
The following $q$ lines each contain two integers $L, R$, representing one query.

Output Format

Output $q$ lines. The $i$-th line contains one integer representing the answer to the $i$-th query.

6 6
1 1 4 5 1 4
1 10
1 5
3 6
4 7
3 9
2 5

19
13
16
16
16
13

10 10
765 523 255 781 647 98 451 636 109 771
394 405
128 161
332 565
996 1003
3 116
403 486
255 582
744 861
399 408
528 996

58
59
69
68
66
62
69
75
58
75

Hint

Sample Explanation

For sample $1$, the maximum is achieved when $x = 10$ in the first query, that is, $\mathrm{popcount}(11)\times 3+\mathrm{popcount}(14)\times 2+\mathrm{popcount}(15)=3\times 3+2\times 3+4=19$.

It is easy to verify that choosing other values of $x$ within the range cannot make the answer larger.

Constraints

This problem uses bundled subtasks.

Let $V$ be the maximum value among the array elements and the query endpoints.

::cute-table | $\text{Subtask}$ | $n\le$ | $q\le$ | $V\le$ |$\text{Score}$ | | :-----------: | :-----------: | :-----------: | :---------: | :----------: | |$1$ | $10$| $10$ | $10$ | $5$ | $2$ |$2$ | $10^5$| $5\times 10^5$ | $10^3$ | $5$ | $2$ |$3$ | ^| $10^5$ | $10^5$ | $15$ | $2$ |$4$ | $10^4$| $10^4$ | $10^9$ | $10$ | $2$ |$5$ | $10^5$| $1$ | ^ | $15$ | $2$ |$6$ | ^| $5\times 10^5$ | ^ | $20$ | $5$ | $7$ | $5\times 10^5$ | $10^5$ | ^ | $20$ | $5$ | $8$ | ^ | $5\times 10^5$ | ^ | $10$ | $2$ | | $9$ | ^ | ^ | $10^{11}$ | $0$ |

For all testdata, it is guaranteed that $1\le n, q\le 5\times 10^5$, $0\le L\le R\le 10^{11}$, and $0\le a_i\le 10^{11}$.

The time limit for subtasks $6, 7, 9$ is $5$ seconds, and for the other subtasks it is $3$ seconds.

Translated by ChatGPT 5