root
       /    \
      c      d
     /        \
    a          o
   / \          \
  t   r          g

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300005;          // 数组最大长度
const int MAXBIT = 30;            // 二进制位数，假设数值小于2^30

// 树节点结构
struct Node {
    int ch[2];   // 两个子节点编号，ch[0]表示走0，ch[1]表示走1
    int cnt;     // 经过该节点的数字个数
} t[MAXN * MAXBIT];               // 节点池，大小 = 版本数 * 位数

int root[MAXN];  // 每个版本对应的根节点编号
int tot;         // 当前已使用的节点总数

// 插入一个数 x，返回新版本根节点编号
// pre 是上一个版本的根节点编号
int insert(int pre, int x) {
    int now = ++tot;              // 新版本根节点编号
    int cur = now;                // cur指向当前正在构建的节点
    for (int i = MAXBIT; i >= 0; i--) {  // 从高位到低位
        int bit = (x >> i) & 1;   // 取出第i位（0或1）
        t[cur] = t[pre];          // 复制旧版本该节点的所有信息（包括ch[0],ch[1],cnt）
        t[cur].ch[bit] = ++tot;   // 为当前位新建一个子节点
        // 复制旧版本对应子节点的信息到新子节点（但cnt还没更新）
        t[t[cur].ch[bit]] = t[t[pre].ch[bit]];
        // 新子节点的计数+1，表示多了一个数经过
        t[t[cur].ch[bit]].cnt++;
        // 继续向下：pre移动到旧版本的相应子节点，cur移动到新版本的子节点
        pre = t[pre].ch[bit];
        cur = t[cur].ch[bit];
    }
    return now;   // 返回新版本根编号
}

// 查询区间 (版本lRoot, 版本rRoot] 中的数与 x 的最大异或值
// 注意：区间内数字 = 版本rRoot包含的数字 - 版本lRoot包含的数字
int query(int lRoot, int rRoot, int x) {
    int res = 0;          // 记录异或结果（最大值）
    int curL = lRoot;     // 指向左版本当前节点
    int curR = rRoot;     // 指向右版本当前节点
    for (int i = MAXBIT; i >= 0; i--) {
        int bit = (x >> i) & 1;      // x的第i位
        int want = bit ^ 1;          // 我们希望走的相反位（0变1，1变0）
        // 计算区间内有多少个数在want分支上
        int cntWant = t[t[curR].ch[want]].cnt - t[t[curL].ch[want]].cnt;
        if (cntWant > 0) {           // 有数可以走want分支
            res |= (1 << i);          // 异或结果的这一位变为1
            curL = t[curL].ch[want]; // 两版本都沿着want走
            curR = t[curR].ch[want];
        } else {                     // 没有数走want，只能走bit分支
            curL = t[curL].ch[bit];
            curR = t[curR].ch[bit];
        }
    }
    return res;
}

int main() {
    int n, q;
    scanf("%d%d", &n, &q);          // 读入数组长度和询问次数

    // 初始化一个空Trie：只有一个根节点，孩子都为0，cnt=0
    tot = 1;                         // 节点编号从1开始
    t[1].ch[0] = t[1].ch[1] = 0;    // 0表示空节点
    t[1].cnt = 0;
    root[0] = 1;                     // 版本0（空版本）的根是1

    // 依次插入数组中的每个数，构建可持久化Trie的前缀版本
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);             // 读入a[i]
        root[i] = insert(root[i-1], x);  // 基于上个版本插入x，得到新版本
    }

    // 处理询问
    while (q--) {
        int l, r, x;
        scanf("%d%d%d", &l, &r, &x); // 读入左端点、右端点和要查询的数
        // 区间[l,r]对应版本l-1和版本r
        printf("%d\n", query(root[l-1], root[r], x));
    }
    return 0;
}

5 3
3 10 5 25 2
1 5 6
2 4 7
1 3 10

31
30
15