题目描述

老师记录了 $n$ 个非负整数编号。对一个编号 $x$，将它写成不含前导零的十六进制表示，其中 $10$ 到 $15$ 分别记为 A 到 F。若该十六进制表示中字母位 A-F 的个数与数字位 0-9 的个数相等，则称 $x$ 为均衡码。特别地，$0$ 的十六进制表示为 0。现在有 $q$ 次询问，每次给出区间 $[l,r]$，请回答该区间内均衡码的数量。

输入格式

第一行包含两个整数 $n$ 和 $q$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

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

输出格式

输出 $q$ 行，每行一个整数，表示对应区间内均衡码的数量。

样例

6 3
10 15 16 31 171 255
1 6
3 4
1 2

1
1
0

样例解释

$10$、$15$、$16$、$31$、$171$、$255$ 的十六进制分别为 A、F、10、1F、AB、FF，其中只有 1F 的字母位和数字位数量相等。因此三个询问的答案分别为 $1$、$1$、$0$。

数据范围

$1 \le n,q \le 100000$，$0 \le a_i \le 65535$，$1 \le l \le r \le n$。

建议使用前缀和在 $O(n+q)$ 时间内完成统计。