思路

考虑对于每个查询，我们先二分找到最小的区间，满足 $k$ 中所有二进制位都存在，这个区间为 $[l, r_1]$

然后判断 $[l, r_1]$ 的区间或运算和是否为 $k$ 即可。

这里的二分中的 check 函数需要枚举 30 个二进制位。

所以我们需要先预处理出每个二进制位的前缀和，这样就可以 $O(1)$ 进行区间二进制位数量的查询。

问题描述

小红是一名魔法师，他有一个由 $n$ 个正整数组成的魔法序列 $A$。现在他想对这个序列施展魔法，每次施展魔法会给出三个正整数 $l,r,k$，小红想知道在区间 $[l,r]$ 中是否存在一个位置 $i$，使得将区间 $[l,i]$ 中的所有数进行按位或运算的结果等于 $k$。如果存在，输出满足条件的最小的 $i$，否则输出 $-1$。

输入格式

第一行包含两个正整数 $n,Q$，表示魔法序列的长度和施展魔法的次数。

第二行包含 $n$ 个正整数 $A_1,A_2,...,A_n$，表示魔法序列 $A$。

接下来 $Q$ 行，每行包含三个正整数 $l,r,k$，表示一次魔法的施展。

输出格式

对于每次施展魔法，输出一行一个整数，表示答案，如果不存在满足条件的位置则输出 $-1$。

样例输入

5 5
3 2 3 3 6
1 2 3
1 5 7
1 4 7
2 2 2
2 3 7

样例输出

1
5
-1
2
-1

评测数据与规模

• $1 \le n,Q \le 10^6$，$1 \le l \le r \le n$，$0 \le A_i, k < 2^{30}$。