给定序列 $a_1,\dots,a_n$，共 $m$ 次查询，每次查询问 $\sum\limits_{i=l}^r 2^{a_i}$ 的二进制表示中 $1$ 的个数。
输入格式
第一行两个数表示 $n,m$。
第二行 $n$ 个数表示 $a_1,\dots,a_n$。
接下来 $m$ 行每行 $l,r$ 表示一次查询。
输出格式
共 $m$ 行，依次为每次查询的答案。
样例数据
样例 1 输入
5 2 2 3 1 2 32 2 5 2 5
样例 1 输出
4 4
子任务
Idea：rushcheyo，Solution：djq_cpp&ccz181078，Code：ccz181078，Data：ccz181078
对于 $100\%$ 的数据，满足 $1\le n\le {10}^5$，$1\le m\le {10}^6$，$1\le a_i\le 10^9$，$1\le l\le r\le n$。
对于 $25\%$ 的数据，满足 $n,m\le 1000$。
对于另外 $25\%$ 的数据，满足 $a_i\le100$。
对于另外 $25\%$ 的数据，满足 $m\le 10^5$
对于另外 $25\%$ 的数据，无特殊限制。