题目描述

给定序列 $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

输入 #1

5 2
2 3 1 2 32
2 5
2 5

输出 #1

4
4

说明/提示

对于 $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\%$ 的数据，无特殊限制。