// 增加一个版本

//root [i] 表示版本号 i 

pre = root[i - 1]; // 首先 pre 指向上一个版本的 root

curr = root[i] = ++ idx;  // 创建一个新的当前版本 curr

// 如果 pre 是空的 说明没有上一个版本 该版本就是最新版

// 如果 pre 不是空的 我们先把 pre 整体克隆一下

if (pre) tree[curr] = tree[pre];

// 完全新增的儿子节点 si 放到 curr 里面；

tree[curr][si] = ++ idx;

// 更新 pre 和 curr 对比下一个节点是需要复制的 还是需要新增的

pre = tree[pre][si], curr = tree[curr][si];

// 接下来只需要循环该操作，完成本次插入的单词

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

// 这里 M 的大小为什么乘以 25 呢？ 因为我们要把 给定序列 a [] 中的整数变成

// 二进制  而 a [i] 的极限值是 10^7 换算成二进制需要 2^24 算上根节点 root 就是 25

// 所以字典树的树高度最多是 25

const int N = 600010, M = N * 25;

int n, m;

int max_id[M];

int tree[M][2], root[N], idx;

int s[N];

//i 表示前缀异或数组 的 下标   也就是当前存储的数字 s [i]

//k 表示当前处理到了二进制的第几位

//pre 表示 数据 s [i] 的第 k 位 上一个版本中的情况 （是否存在？）

//curr 表示当前版本

void insert(int i, int k, int pre, int curr) {

    // 整个数字插入完毕 记录它是第 i 个被插入的数

    if (k < 0) {

        max_id[curr] = i;

        return ;

    }

    //s [i] 为插入数字 取出第 k 位

    int v = s[i] >> k & 1;

    // 数据 s [i] 的第 k 位 存在于上一个版本中的  

    // 则把上一个版本中的 其他位 复制过来

    if (pre) tree[curr][v ^ 1] = tree[pre][v ^ 1];

    // 把当前位 创建出来

    tree[curr][v] = ++ idx;

    // 递归创建 下一个二进制位 即 k-1

    insert(i, k - 1, tree[pre][v], tree[curr][v]);

    // 因为当前位 max_id 的更新 需要子节点的数据 

    // 所以当递归到底的时候 要自底向上的更新当前的 max_id

    max_id[curr] = max(max_id[tree[curr][0]], max_id[tree[curr][1]]);

}

//root 表示某个版本的根节点 也就是 右端点

//c 表示当前用来查询的值  也就是 s [n] ^ x 的结果

//l 表示左端点的限制

int query(int root, int c, int l) {

    // 查询 就和 标准的字典树查询非常的相似了

    int pre = root;

    // 需要注意的是 这里 直接用 23 个二进制位 来构建 [l,r] 中的一个数就行

    for (int i = 23; i >= 0; i -- ) {

        int v = c >> i & 1;  //c 的第 i 位

        // 那么要找的就是 v^1  如果有符合条件的 根节点下的 v^1 就选择

        // 注意我们的 max_id 默认为 - 1 如此肯定不会 >=l  

        // 如果 max_id 默认为 0 则 l 也是 0  就会跳到不存在的节点

        if (max_id[tree[pre][v ^ 1]] >= l) pre = tree[pre][v ^ 1];

        // 否则 只能使用 v 了

        else pre = tree[pre][v];

    }

    //max_id [pre] 就是我们最终找到的 s [] 中的下标 与上 c 就是最终结果

    return c ^ s[max_id[pre]];

}

int main() {

    cin >> n >> m;

    max_id[0] = -1;  // 初始化根节点的 max_id

    root[0] = ++ idx;

    // 首先插入一下 根节点也就是 s [0] （注意 s [0] 的值是 0）

    insert(0, 23, 0, root[0]);  

    // 读取整个序列 并以 持久化的方式 插入到字典树

    for (int i = 1; i <= n; i ++ ) {

        int x;

        scanf("%d", &x);

        s[i] = s[i - 1] ^ x;  // 求 异或前缀数组

        // 每插入一个数字 都是一个新的版本

        root[i] = ++ idx;

        insert(i, 23, root[i - 1], root[i]);

    }

    char op[2];

    int l, r, x;

    while (m -- ) {

        scanf("%s", op);

        if (*op == 'A') {

            // 插入一个数字到末尾

            scanf("%d", &x);

            n ++ ;

            s[n] = s[n - 1] ^ x;

            root[n] = ++ idx;

            insert(n, 23, root[n - 1], root[n]);

        } else {

            scanf("%d%d%d", &l, &r, &x);

            // 查询中要注意的是 我们想查的是在原数组 [l,r] 中找到 p

            // 但是 我们使用了 前缀异或数组 它的第一位 s [0]=0 在原数组中不存在

            // 也就是说 是有一位下标偏移的

            // 所以在原数组中找 [l,r]  前缀异或数组 中对应的是 [l-1, r-1]

            printf("%d\n", query(root[r - 1], s[n] ^ x, l - 1));

        }

    }

    return 0;

}

#include <cstring>

#include <algorithm>

#include <iostream>

#include <vector>

using namespace std;

const int N = 100010, M = 10010;

int a[N];

vector<int> nums;

int n, m;

// 节点数量 除了原来的 N*4 之外

// 还要算上持久化用到的  N * logN

struct Node {

    int l, r;

    int cnt;

}tree[N * 4 + N * 17];

int root[N], idx;

int find(int x) {

    return lower_bound(nums.begin(), nums.end(), x) - nums.begin();

}

// 初始化 线段树的整体结构 每个数字的插入使用 insert

int build(int l, int r) {

    int curr = ++ idx;

    if (l == r) return curr;

    int mid = l + r >> 1;

    tree[curr].l = build(l, mid), tree[curr].r = build(mid + 1, r);

    return curr;

}

//pre 表示上一个根节点

//l 和 r 表示增加的左右端点 

//x 表示的是要增加的数 离散化后的位置

int insert(int pre, int l, int r, int x) {

    // 插入的过程类似 持久化字典树

    // 增加一个新的当前版本

    int curr = ++ idx;

    // 先复制上一个版本到当前版本

    tree[curr] = tree[pre];

    // 区间长度为 1 的时候 就是 x 的位置 把 x 放在这里 当前版本 curr 的 cnt++

    // 要注意的是 线段树只是保存区间里面的元素个数 

    // 所以插入其实就是找到对应的位置然后 cnt 增加

    if (l == r) {

        tree[curr].cnt ++ ;

        return curr;

    }

    int mid = l + r >> 1;

    // 插入的数 小于 mid 则插入到左面 否则插入到右面

    // 递归插入的时候 也要注意这里的细节  是递归插入到了子节点 而非 pre

    if (x <= mid) tree[curr].l = insert(tree[pre].l, l, mid, x);

    else tree[curr].r = insert(tree[pre].r, mid + 1, r, x);

    // 这里的细节一定要注意  我在这写错了  debug 了很久很久。。。

    // 这块其实就相当于 线段树中的 pushup 操作了  子节点计算根节点

    // 而 curr 的两个子节点 其实是 tree [curr].l 和 tree [curr].r

    tree[curr].cnt = tree[tree[curr].l].cnt + tree[tree[curr].r].cnt;

    return curr;

}

// 其中 R 表示 [1, R] 版本 root [R] 包含的所有数

// L 表示 左边界的 L 我们需要剔除 [1,L-1]

//l 和 r 分别表示当前查询的左右边界 k 即题目给出的 k

int query(int R, int L, int l, int r, int k) {

    // 我们一直保证 [l,r] 中包含答案，那么如果只有一个数 那么这个数就是答案

    if (l == r) return r;

    //tree [tree [R].l].cnt 表示存在于 R 的左子树里面数的个数

    //tree [tree [L].l].cnt 表示存在于 L 的左子树里面数的个数

    // 两者相减 表示 存在于 R 的左子树 但是不包含在 [1, L] 中的数的个数

    int cnt = tree[tree[R].l].cnt - tree[tree[L].l].cnt;

    int mid = l + r >> 1;

    // 如果 k 在 cnt 之内  递归到左面 也就是 [tree [L].l, tree [R].l ]

    if (k <= cnt) return query(tree[R].l, tree[L].l, l, mid, k);

    // 否则 递归到右边  注意递归到右边之后 所求的 k 在右边是 k-cnt

    else return query(tree[R].r, tree[L].r, mid + 1, r, k - cnt);

}

int main() {

    cin >> n >> m;

    for (int i = 1; i <= n; i ++ ) {

        scanf("%d", &a[i]);

        nums.push_back(a[i]);  // 离散化 先放到 nums

    }

    // 离散化

    sort(nums.begin(), nums.end());

    nums.erase(unique(nums.begin(), nums.end()), nums.end());

    root[0] = build(0, nums.size() - 1);  // 初始化一下节点 0

    // 插入一个数就算一个版本

    for (int i = 1; i <= n; i ++ )

        root[i] = insert(root[i - 1], 0, nums.size() - 1, find(a[i]));

    while (m -- ) {

        int l, r, k;

        scanf("%d%d%d", &l, &r, &k);

        printf("%d\n", nums[query(root[r], root[l - 1], 0, nums.size() - 1, k)]);

    }

    return 0;

}