题目背景

题目描述

久岛鸥给了你一个长度为 $n$ 的非负整数序列 $a_{1\sim n}$。

接下来有 $q$ 次询问，每次询问给出非负整数 $L,R$，求

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

其中 $\mathrm{popcount}(x)$ 表示 $x$ 在二进制形式下数位 $1$ 的出现次数。

输入格式

第一行，两个整数 $n,q$。
第二行给出 $n$ 个整数代表序列 $a_{1\sim n}$。
随后 $q$ 行，每行两个整数 $L,R$，代表一次询问。

输出格式

输出 $q$ 行，第 $i$ 行一个整数代表第 $i$ 次询问的答案。

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

提示

样例解释

对于样例 $1$，第一组询问取 $x=10$ 时达到最大值，即 $\mathrm{popcount}(11)\times 3+\mathrm{popcount}(14)\times 2+\mathrm{popcount}(15)=3\times 3+2\times 3+4=19$。

容易验证 $x$ 取范围内其他值都不能使答案更大。

数据范围

本题开启捆绑测试。

令 $V$ 为数组中元素与询问区间端点的最大值。

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

对于所有数据，保证 $1\le n,q\le 5\times 10^5$，$0\le L\le R\le 10^{11}$，$0\le a_i\le 10^{11}$。

子任务 $6,7,9$ 的时间限制为 $5$ 秒，其余子任务均为 $3$ 秒。