Lưu ý: Ngoài nhiệm vụ con đầu tiên, giới hạn bộ nhớ của bài toán này là 60MB.

Zhengxu Sakiko là một vận động viên thi đấu thuật toán nổi tiếng. Tuy nhiên, vì trí nhớ kém, anh ấy thường xuyên quên mất các thuật toán mình đã học.

Đó là lý do tại sao anh ấy thường xuyên hồi tưởng về quá khứ.

Vui lòng lưu ý giới hạn bộ nhớ đặc biệt của bài toán này.

Cho $m$ bộ ba $(l,r,v)$.

Có $q$ truy vấn, mỗi truy vấn cho trước $x,y$, yêu cầu tìm giá trị $v$ lớn nhất trong các bộ ba thỏa mãn $l\le x\le r$ và $v\le y$.

Nếu không tồn tại bộ ba nào thỏa mãn điều kiện, in ra $0$.

Bài toán này yêu cầu xử lý trực tuyến (online).

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $m,q$.

$m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên biểu diễn một bộ ba $(l,r,v)$.

$q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $p,q$ biểu diễn truy vấn hiện tại, trong đó $x=p\oplus ans$ và $y=q\oplus ans$. Ở đây $\oplus$ là phép toán XOR, và $ans$ là giá trị của câu trả lời truy vấn trước đó được thực hiện phép toán AND với $2^{21}-1$. Giá trị $ans$ ban đầu bằng $0$.

Dữ liệu ra

Với mỗi truy vấn, in ra một dòng chứa câu trả lời.

Ví dụ

Dữ liệu vào 1

5 5
3 5 3
4 5 10
3 4 2
1 4 13
1 1 6
1 6
7 11
9 14
2 1
5 14

Dữ liệu ra 1

6
13
3
0
10

Dữ liệu vào 2

15 15
3 9 9
3 5 10
8 15 10
4 6 4
8 13 6
3 7 0
11 11 11
8 10 11
3 3 14
3 15 13
4 15 9
6 11 7
4 5 12
6 12 10
10 10 14
9 5
1 5
8 11
14 9
8 14
3 11
7 1
4 3
3 1
12 15
9 4
13 15
0 3
13 12
6 13

Dữ liệu ra 2

0
0
11
0
13
0
0
0
0
13
9
4
4
7
0

Giới hạn

Với tất cả dữ liệu: $1\le m,q\leq 10^6, 1\le l\le r\le 2\times 10^6, 0\le v<2^{31}, 1\leq x\leq 2\times 10^6, 0\leq y< 2^{31}$.

Ghi chú

Ngoài ra, đây là đoạn mã tìm phần tử nhỏ thứ $k$ trong đoạn do tiểu Z viết, có thể hữu ích cho bạn.

#include <bits/stdc++.h>
using namespace std;
constexpr int Spp{1<<20},S2{1<<20};
char buf[Spp],*p1,*p2,buf2[S2],*l2=buf2,_st[22];
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,Spp,stdin),p1==p2)?EOF:*p1++)
#define putchar(c) (l2==buf2+S2&&(fwrite(buf2,1,S2,stdout),l2=buf2),*l2++=(c))
template <typename T>
void read(T &x) {
    char c;int f{1};
    do x=(c=getchar())^48;
    while (!isdigit(c)&&c!='-');
    if (x==29) f=-1,x=0;
    while (isdigit(c=getchar()))
        x=(x*10)+(c^48);
    x*=f;
}
template <typename T,typename ...Args>
void read(T& x,Args&... args) {read(x);read(args...);}
template<typename T>
void write(T x,char c='\n') {
    if (x<0) putchar('-'),x*=-1;
    int tp=0;
    do _st[++tp]=x%10; while (x/=10);
    while (tp) putchar(_st[tp--]+'0');
    putchar(c);
}
struct OI{~OI(){fwrite(buf2,1,l2-buf2,stdout);}}oi;
using LL=unsigned long long;
// wavelet
struct bits {
    vector<LL> bl;
    vector<int> c;
    void resize(int num) {
        bl.resize(((num+1)>>6)+1);
        c.resize(bl.size());
    }
    void set(int i,LL val) {bl[i>>6]|=(val<<(i&63));}
    void build() {
        for (int i=1;i<bl.size();++i)
            c[i]=c[i-1]+popcount(bl[i-1]);
    }
    int rk1(int i) {return c[i>>6]+popcount(bl[i>>6]&((1uLL<<(i&63))-1));}
    int rk0(int i) {return i-rk1(i);}
};
struct wavelet {
    int h;
    vector<bits> B;
    vector<int> pos;
    void init(vector<int>& v) {
        h=__lg(*max_element(v.begin(),v.end()))+1;
        B.resize(h);pos.resize(h);
        for (int i=0;i<h;++i) {
            B[i].resize(v.size());
            for (int j=0;j<v.size();++j)
                B[i].set(j,(v[j]>>(h-i-1)&1));
            B[i].build();
            pos[i]=stable_partition(v.begin(),v.end(),[&](int c){
                return !(c>>(h-i-1)&1);
            })-v.begin();
        }
    }
    int qry(int i,int j,int k,int l,int r,int x) {
        if (i==j) return 0;
        if (r==l+1) return l;
        int mid=l+r>>1;
        int L{B[x].rk0(i)},R{B[x].rk0(j)};
        if (R-L>=k) return qry(L,R,k,l,mid,x+1);
        else return qry(pos[x]+B[x].rk1(i),pos[x]+B[x].rk1(j),k-(R-L),mid,r,x+1);
    }
} tr;
int main() {
    int n,m;read(n,m);
    vector<int> a(n);
    for (int i=0;i<n;++i) read(a[i]);
    tr.init(a);
    while (m--) {
        int l,r,k;read(l,r,k);
        write(tr.qry(l-1,r,k,0,1<<tr.h,0));
    }
    return 0;
}