题目描述

如果一个正整数的二进制表示包含奇数个 $1$，则称它为"有趣的"。

给定 $n$ 个正整数 $A_1,A_2,\ldots,A_n$，有 $q$ 次询问，每次询问给出区间 $[l,r]$，求区间内所有"有趣的"数字之和。

输入格式

第一行两个正整数 $n,q$。

第二行 $n$ 个正整数 $A_1,A_2,\ldots,A_n$。

接下来 $q$ 行，每行两个正整数 $l,r$，表示一次询问。

输出格式

输出 $q$ 行，每行一个整数，表示对应区间内所有"有趣的"数字之和。

样例

6 2
1 2 3 4 5 6
1 3
2 6

4
8

样例解释

$1$ 的二进制为 $1$（$1$ 个 $1$，有趣） $2$ 的二进制为 $10$（$1$ 个 $1$，有趣） $3$ 的二进制为 $11$（$2$ 个 $1$，不有趣） $4$ 的二进制为 $100$（$1$ 个 $1$，有趣） $5$ 的二进制为 $101$（$2$ 个 $1$，不有趣） $6$ 的二进制为 $110$（$2$ 个 $1$，不有趣）

第一次询问 $[1,3]$，有趣的是 $1+2=4$。 第二次询问 $[2,6]$，有趣的是 $2+4=8$。

数据范围

对于 $100\%$ 的测试点，$1 \le n,q \le 10^5$，$1 \le A_i \le 10^9$。