题目描述

有一列长度为 $n$ 的非负整数，每个整数都在 $0$ 到 $255$ 之间。对一个整数而言，若它的二进制表示中第 $k$ 位为 $1$，则称它具有第 $k$ 个位标记。最低位为第 $0$ 位。

现在有 $q$ 次查询，每次给出 $l$、$r$、$k$，请统计下标从 $l$ 到 $r$ 的所有整数中，有多少个整数具有第 $k$ 个位标记。

输入格式

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

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

接下来 $q$ 行，每行包含三个整数 $l$、$r$、$k$，表示一次查询。

输出格式

输出 $q$ 行，每行一个整数，表示对应查询的统计结果。

样例

6 4
5 2 7 8 3 10
1 3 0
2 6 1
4 6 3
1 6 2

2
4
2
2

样例解释

例如第 $1$ 次查询区间为 $1$ 到 $3$，对应 $5$、$2$、$7$，其中 $5$ 和 $7$ 的第 $0$ 位为 $1$，所以答案为 $2$。其他查询按同样规则统计。

数据范围

对于 $30\%$ 的数据，满足 $1 \le n,q \le 100$。

对于全部数据，满足 $1 \le n,q \le 100000$，$0 \le a_i \le 255$，$1 \le l \le r \le n$，$0 \le k \le 7$。