Problem: I - The J-th Number

Problem Statement

You are given N empty arrays, t_1, ..., t_n. At first, you execute M queries as follows.

* add a value v to array t_i (a \leq i \leq b)



Next, you process Q following output queries.

* output the j-th number of the sequence sorted all values in t_i (x \leq i \leq y)



Input

The dataset is formatted as follows.


N M Q
a_1 b_1 v_1
...
a_M b_M v_M
x_1 y_1 j_1
...
x_Q y_Q j_Q


The first line contains three integers N (1 \leq N \leq 10^9), M (1 \leq M \leq 10^5) and Q (1 \leq Q \leq 10^5). Each of the following M lines consists of three integers a_i, b_i and v_i (1 \leq a_i \leq b_i \leq N, 1 \leq v_i \leq 10^9). Finally the following Q lines give the list of output queries, each of these lines consists of three integers x_i, y_i and j_i (1 \leq x_i \leq y_i \leq N, 1 \leq j_i \leq Σ_{x_i \leq k \leq y_i} |t_k|).

Output

For each output query, print in a line the j-th number.

Sample Input 1


5 4 1
1 5 1
1 1 3
4 5 1
3 4 2
1 3 4


Output for the Sample Input 1


2


After the M-th query is executed, each t_i is as follows:


[1,3], [1], [1,2], [1,1,2], [1,1]


The sequence sorted values in t_1, t_2 and t_3 is [1,1,1,2,3]. In the sequence, the 4-th number is 2.

Sample Input 2


10 4 4
1 4 11
2 3 22
6 9 33
8 9 44
1 1 1
4 5 1
4 6 2
1 10 12


Output for the Sample Input 2


11
11
33
44






Example

Input

5 4 1
1 5 1
1 1 3
4 5 1
3 4 2
1 3 4


Output

2

Solution (in CPP):

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int N,M,Q;
int A[111111],B[111111],V[111111];

int L[111111],R[111111],J[111111];

const int SEG=1<<19;
int sum[SEG*2],put[SEG*2],len[SEG*2];

void init(vint &xs){
    memset(sum,0,sizeof(sum));
    memset(put,0,sizeof(put));
    memset(len,0,sizeof(len));

    for(int i=0;i+1<xs.size();i++){
        len[i+SEG-1]=xs[i+1]-xs[i];
    }

    for(int i=SEG-2;i>=0;i--){
        len[i]=len[i*2+1]+len[i*2+2];
    }
}

inline void push(int k){
    sum[k]+=put[k]*len[k];
    if(k<SEG-1){
        put[k*2+1]+=put[k];
        put[k*2+2]+=put[k];
    }
    put[k]=0;
}

void add(int a,int b,int k=0,int l=0,int r=SEG){
    push(k);
    if(r<=a||b<=l)return;
    if(a<=l&&r<=b){
        put[k]++;
        push(k);
        return;
    }
    add(a,b,k*2+1,l,(l+r)/2);
    add(a,b,k*2+2,(l+r)/2,r);
    sum[k]=sum[k*2+1]+sum[k*2+2];
}

int query(int a,int b,int k=0,int l=0,int r=SEG){
    push(k);
    if(r<=a||b<=l)return 0;
    if(a<=l&&r<=b)return sum[k];
    return query(a,b,k*2+1,l,(l+r)/2)+query(a,b,k*2+2,(l+r)/2,r);
}


signed main(){
    scanf("%lld%lld%lld",&N,&M,&Q);

    vector<tuple<int,int,int>>ops;
    rep(i,M){
        int a,b,v;
        scanf("%lld%lld%lld",&a,&b,&v);
        a--;
        ops.pb(make_tuple(v,a,b));
    }
    sort(all(ops));
    rep(i,M)tie(V[i],A[i],B[i])=ops[i];


    rep(i,Q)scanf("%lld%lld%lld",&L[i],&R[i],&J[i]),L[i]--;

    vector<int>xs;
    xs.pb(0);xs.pb(N);
    rep(i,M){
        xs.pb(A[i]);
        xs.pb(B[i]);
    }
    rep(i,Q){
        xs.pb(L[i]);
        xs.pb(R[i]);
    }
    sort(all(xs));xs.erase(unique(all(xs)),xs.end());
    rep(i,M){
        A[i]=lower_bound(all(xs),A[i])-xs.begin();
        B[i]=lower_bound(all(xs),B[i])-xs.begin();
    }

    rep(i,Q){
        L[i]=lower_bound(all(xs),L[i])-xs.begin();
        R[i]=lower_bound(all(xs),R[i])-xs.begin();
    }

    vint lb(Q),ub(Q,M);

    while(true){
        vpint qs;
        rep(i,Q){
            if(lb[i]+1==ub[i])continue;
            int mid=(ub[i]+lb[i])/2;
            qs.pb({mid,i});
        }
        if(qs.size()==0)break;
        sort(all(qs));
        int cur=0;

        init(xs);
        for(int i=0;i<M;i++){
            while(cur<qs.size()&&qs[cur].fi<=i){
                int m,k;
                tie(m,k)=qs[cur++];
                if(query(L[k],R[k])>=J[k])ub[k]=m;
                else lb[k]=m;
            }
            add(A[i],B[i]);
        }
    }

    rep(i,Q){
        printf("%lld\n",V[lb[i]]);
    }
    return 0;
}