问题描述

塔子哥是一名魔法师，他有一个由 $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}$。