Problem Description

Given a sequence $a_1,\dots,a_n$ and $m$ queries, each query asks for the number of $1$ bits in the binary representation of $\sum\limits_{i=l}^r 2^{a_i}$.

Input Format

The first line contains two integers $n, m$.

The second line contains $n$ integers $a_1,\dots,a_n$.

The next $m$ lines each contain $l, r$, representing one query.

Output Format

Output $m$ lines. Each line is the answer to the corresponding query.

5 2
2 3 1 2 32
2 5
2 5

4
4

Hint

Idea: rushcheyo, Solution: djq_cpp&ccz181078, Code: ccz181078, Data: ccz181078.

Constraints: For $100\%$ of the testdata, $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$.

For $25\%$ of the testdata, $n, m\le 1000$.

For another $25\%$ of the testdata, $a_i\le 100$.

For another $25\%$ of the testdata, $m\le 10^5$.

For the remaining $25\%$ of the testdata, there are no special constraints.

Translated by ChatGPT 5