주의: 이 문제는 첫 번째 서브태스크를 제외하고 60MB의 메모리 제한이 있습니다.

문제 배경

Zhengxu Sakiko는 유명한 알고리즘 경시 대회 참가자입니다. 하지만 그는 기억력이 너무 나빠서 배운 알고리즘을 자주 잊어버리곤 합니다.

이것이 바로 그가 종종 과거를 추억하는 이유입니다.

문제

이 문제의 특별한 메모리 제한에 유의하십시오.

$m$개의 삼중항 $(l, r, v)$가 주어집니다.

$q$개의 연산이 주어지며, 각 연산마다 $x, y$가 주어집니다. 이는 $l \le x \le r$이고 $v \le y$를 만족하는 삼중항들 중에서 $v$의 최댓값을 구하라는 의미입니다.

조건을 만족하는 삼중항이 존재하지 않으면 $0$을 출력합니다.

이 문제는 강제 온라인(forced online) 방식입니다.

입력

첫 번째 줄에 두 정수 $m, q$가 주어집니다.

다음 $m$개의 줄에는 각 삼중항 $(l, r, v)$를 나타내는 세 정수가 주어집니다.

다음 $q$개의 줄에는 각 질의를 나타내는 두 정수 $p, q$가 주어집니다. 현재 질의는 $x = p \oplus ans$, $y = q \oplus ans$를 만족하며, 여기서 $\oplus$는 비트 단위 XOR 연산이고, $ans$는 이전 질의의 결과값과 $2^{21}-1$을 비트 단위 AND 연산한 값입니다. 초기 $ans$는 $0$입니다.

출력

각 질의에 대해 한 줄에 하나씩 답을 출력합니다.

예제

입력 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

출력 1

6
13
3
0
10

입력 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

출력 2

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

제한

모든 데이터에 대하여: $1 \le m, q \le 10^6$, $1 \le l \le r \le 2 \times 10^6$, $0 \le v < 2^{31}$, $1 \le x \le 2 \times 10^6$, $0 \le y < 2^{31}$입니다.

참고

참고로, 여기 작은 Z가 작성한 구간 $k$번째 작은 값(k-th smallest value)을 구하는 코드가 있으며, 문제 해결에 도움이 될 수 있습니다.

#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;
}