Примечание: за исключением первого подзадачи, ограничение по памяти в этой задаче составляет 60 МБ.

Предыстория

Чжэнсюй Сакико — известный участник олимпиад по программированию. Однако из-за плохой памяти он часто забывает изученные алгоритмы.

Вот почему он часто вспоминает прошлое.

Пожалуйста, обратите внимание на особые ограничения по памяти в этой задаче.

Дано $m$ троек $(l, r, v)$.

Имеется $q$ запросов. Каждый запрос задается парой $(x, y)$ и требует найти максимальное значение $v$ среди всех троек, для которых выполняются условия $l \le x \le r$ и $v \le y$.

Если троек, удовлетворяющих условиям, не существует, выведите $0$.

Задача должна быть решена в режиме онлайн (ответ на текущий запрос зависит от предыдущего).

Входные данные

В первой строке содержатся два целых числа $m$ и $q$.

Далее следуют $m$ строк, каждая из которых содержит три целых числа, описывающих тройку $(l, r, v)$.

Затем следуют $q$ строк, каждая из которых содержит два целых числа $p$ и $q$. Текущий запрос определяется как $x = p \oplus ans$ и $y = q \oplus ans$, где $\oplus$ — операция побитового исключающего ИЛИ, а $ans$ — результат предыдущего запроса, побитово умноженный на $2^{21}-1$ (операция &). Изначально $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}$.

Примечание

Кроме того, здесь приведен код для поиска $k$-го наименьшего элемента в диапазоне, написанный Сяо Зэ, который может оказаться полезным.

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