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

Input

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

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

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

Output

Output $m$ lines, each containing the answer to the corresponding query.

Examples

Input 1

5 2
2 3 1 2 32
2 5
2 5

Output 1

4
4

Subtasks

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

For $100\%$ of the data, $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 data, $n, m\le 1000$.

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

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

For the remaining $25\%$ of the data, there are no special restrictions.