题目描述 数字在计算机中是以二进制存储的，小 Z 在监控程序运行状态。他想知道给定一个掩码，一段内存中有多少个数可以匹配该掩码。 匹配定义：待匹配数为 $a$，掩码为 $b$，若 $b$ 的二进制表示中所有的 $1$，在 $a$ 的二进制表示的相对应位置也为 $1$，则称 $a$ 可以匹配掩码 $b$。 例如，$1$ 为掩码，其二进制表示为 "$1$"，则 $1(1)$，$3(11)$，$5(101)$，$7(111)$，……均可匹配该掩码，括号内为该数字对应二进制表示。 又例如，$13$ 的二进制为 "$1101$"，如果掩码为 $12$，$12$ 的二进制为 "$1100$"，掩码 $12$ 可以匹配数字 $13$。同时该掩码也可以匹配数字 $15(1111)$。 为了简化问题，小Z所有的掩码保证二进制下 $1$ 的个数不超过 $2$ 个。 输入格式 第一行包含一个整数 $n$，表示观测的内存长度，编号从 $1$ 到 $n$。 第二行包含 $n$ 个整数表示内存中存储的数。 第三行包含一个整数 $q$ 表示询问数量。 接下来 $q$ 行每行包含三个整数 $s$、$t$ 和 $m$，表示从位置 $s$ 到位置 $t$，掩码为 $m$。 输出格式 对于每次询问，输出一个整数表示从 $s$ 到 $t$（包含起点和终点），可有多少数字可以匹配掩码 $m$。 数据范围 $1 \leq n \leq 20000$ $1 \leq q \leq 100000$ $m > 0$ 且保证二进制下至多两位为 $1$ 内存中储存的数字范围为 $[1, 10^8]$ 输入样例 8 1 2 3 4 5 6 7 8 3 1 8 3 1 8 1 1 8 6 输出样例 2 4 2