#include <bits/stdc++.h>

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
//cut begin
template <typename T,typename E>
struct LazySegmentTree{
private:
    typedef std::function<T(T,T)> F;
    typedef std::function<T(T,E)> G;
    typedef std::function<E(E,E)> H;
    typedef std::function<E(E,int)> P;
    int n;
    F cal;//function for merge
    G upd;//function for update
    H ecal;//function for evaluate
    std::vector<T> init;
    E opinit;
    P rcal;//function for range calculate
    T initv;
    std::vector<T> node;
    std::vector<E> lazy;
public:
    explicit LazySegmentTree(//配列で初期化する場合
            int sz,
            F cal,
            G upd,
            H ecal,
            std::vector<T> init=std::vector<T>(1,0),
            E opinit=0,
            P rcal=[](T a,int b){return a;}
    ):
    cal(cal),
    upd(upd),
    ecal(ecal),
    init(init),
    opinit(opinit),
    rcal(rcal)
    {
        n=1;
        initv=init[0];
        while(n<sz)n=n*2;
        node.assign(static_cast<unsigned int>(2 * n - 1), init[0]);//はみ出る分は0番地に指定
        for (int i = 0; i <sz ; ++i) node[i+n-1]=init[i+1];
        for (int i = n-2; i >= 0 ; --i) node[i]=cal(node[2*i+1],node[2*i+2]);

        lazy.resize(static_cast<unsigned int>(2 * n - 1), opinit);
        for (int i = 0; i <sz ; ++i) lazy[i+n-1]=opinit;
        for (int i = n-2; i >= 0 ; --i) lazy[i]=ecal(lazy[2*i+1],lazy[2*i+2]);
    }

    void update(int p,int q,E val,int k=0,int l=0,int r=-1){//[p,q):0-indexed
        if(r<0)r=n;
        eval(k,r-l);
        if(r<=p||l>=q)return;
        if(p<=l&&r<=q){
            lazy[k]=ecal(lazy[k],val);
            eval(k,r-l);
        }
        else{
            update(p,q,val,2*k+1,l,(l+r)/2);
            update(p,q,val,2*k+2,(l+r)/2,r);
            node[k]=cal(node[2*k+1],node[2*k+2]);
        }
    }

    T query(int p,int q,int k=0,int l=0,int r=-1){//[p,q):0-indexed
        if(r<0)r=n;
        if(r<=p||l>=q)return initv;

        eval(k,r-l);
        if(p<=l&&r<=q)return node[k];
        T vl=query(p,q,2*k+1,l,(l+r)/2);
        T vr=query(p,q,2*k+2,(l+r)/2,r);
        return cal(vl,vr);
    }

    void eval(int k,int len){//k:0-indexed
        if(lazy[k]==opinit)return;
        node[k]=upd(node[k],rcal(lazy[k],len));
        if(k<n-1){
            lazy[2*k+1]=ecal(lazy[2*k+1],lazy[k]);
            lazy[2*k+2]=ecal(lazy[2*k+2],lazy[k]);
        }
        lazy[k]=opinit;
    }
};

using namespace std;
using ll = long long;
using pi = pair<int,int>;
int main() {
    int n,m,q;
    cin>>n>>m>>q;
    vector<pi> init(n+1);
    init[0]=pi(0,n+10);
    for(int i = 1;i <= n;++i) {
        init[i]=pi(i-1,i-1);
    }
    vector<pair<pi,pi>> event;
    for(int i = 0;i < m;++i) {
        int d,a,b;
        cin>>d>>a>>b;
        --a;--b;
        event.emplace_back(pi(d,1),pi(a,b+1));
    }
    vector<bool> ans(q,false);
    map<pair<int,pi>,int> mp;
    for(int i = 0;i < q;++i) {
        int e,s,t;
        cin>>e>>s>>t;
        --s;--t;
        event.emplace_back(pi(e,0),pi(s,t));
        mp[make_pair(e,pi(s,t))]=i;
    }
    sort(event.begin(),event.end());
    LazySegmentTree<pi,pi> st(
        n,
        [](pi a,pi b){return pi(max(a.first,b.first),min(a.second,b.second));},
        [](pi a,pi b){return b;},
        [](pi a,pi b){return pi(max(a.first,b.first),min(a.second,b.second));},
        init,
        pi(0,n+10)
    );
    for(auto t:event) {
        int d=t.first.first;
        int op=t.first.second;
        int l=t.second.first;
        int r=t.second.second;
        if(op==0) {
            auto tv = st.query(l,l+1);
            //cerr<<tv<<endl;
            ans[mp[make_pair(d,pi(l,r))]]= (tv.first>=r);
        }
        else {
            auto tv = st.query(l,l+1);
            auto mv=st.query(tv.second,r);
            //cerr<<mv.first<<" "<<mv.second<<endl;
            st.update(min(l,mv.second),r,pi(mv.first,min(l,mv.second)));
        }
    }
    for(int i = 0;i < q;++i) {
        if(ans[i])cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}


### Prompt

Generate a Cpp solution to the following problem:

problem

AOR Co., Ltd. is a $ N $ story building. There is no basement floor.
AOR Ika-chan is a squid, so she can go down the stairs, but not up.

I decided to install $ M $ elevators in the building because it would be inconvenient if I couldn't climb upstairs.
It takes time to install the elevator, and the $ i $ th elevator will be installed the night after $ D_i $ and will be mobile on all floors above the $ A_i $ floor and below the $ B_i $ floor.

You were asked $ Q $ questions by AOR Ika-chan. The $ i $ th question is, "Can I move from the $ S_i $ floor to the $ T_i $ floor at noon $ E_i $ days later?"
The only means of transportation are stairs and elevators. In addition, the time required for movement shall be negligible.



input

$ N \ M \ Q $
$ D_1 \ A_1 \ B_1 $
$ \ vdots $
$ D_M \ A_M \ B_M $
$ E_1 \ S_1 \ T_1 $
$ \ vdots $
$ E_Q \ S_Q \ T_Q $

output

Print Yes or No on one line for each question. However, answer in the order in which they are asked. Also, output a line break at the end.

Example

Input

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


Output

No
Yes

### Response

```cpp
#include <bits/stdc++.h>

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
//cut begin
template <typename T,typename E>
struct LazySegmentTree{
private:
    typedef std::function<T(T,T)> F;
    typedef std::function<T(T,E)> G;
    typedef std::function<E(E,E)> H;
    typedef std::function<E(E,int)> P;
    int n;
    F cal;//function for merge
    G upd;//function for update
    H ecal;//function for evaluate
    std::vector<T> init;
    E opinit;
    P rcal;//function for range calculate
    T initv;
    std::vector<T> node;
    std::vector<E> lazy;
public:
    explicit LazySegmentTree(//配列で初期化する場合
            int sz,
            F cal,
            G upd,
            H ecal,
            std::vector<T> init=std::vector<T>(1,0),
            E opinit=0,
            P rcal=[](T a,int b){return a;}
    ):
    cal(cal),
    upd(upd),
    ecal(ecal),
    init(init),
    opinit(opinit),
    rcal(rcal)
    {
        n=1;
        initv=init[0];
        while(n<sz)n=n*2;
        node.assign(static_cast<unsigned int>(2 * n - 1), init[0]);//はみ出る分は0番地に指定
        for (int i = 0; i <sz ; ++i) node[i+n-1]=init[i+1];
        for (int i = n-2; i >= 0 ; --i) node[i]=cal(node[2*i+1],node[2*i+2]);

        lazy.resize(static_cast<unsigned int>(2 * n - 1), opinit);
        for (int i = 0; i <sz ; ++i) lazy[i+n-1]=opinit;
        for (int i = n-2; i >= 0 ; --i) lazy[i]=ecal(lazy[2*i+1],lazy[2*i+2]);
    }

    void update(int p,int q,E val,int k=0,int l=0,int r=-1){//[p,q):0-indexed
        if(r<0)r=n;
        eval(k,r-l);
        if(r<=p||l>=q)return;
        if(p<=l&&r<=q){
            lazy[k]=ecal(lazy[k],val);
            eval(k,r-l);
        }
        else{
            update(p,q,val,2*k+1,l,(l+r)/2);
            update(p,q,val,2*k+2,(l+r)/2,r);
            node[k]=cal(node[2*k+1],node[2*k+2]);
        }
    }

    T query(int p,int q,int k=0,int l=0,int r=-1){//[p,q):0-indexed
        if(r<0)r=n;
        if(r<=p||l>=q)return initv;

        eval(k,r-l);
        if(p<=l&&r<=q)return node[k];
        T vl=query(p,q,2*k+1,l,(l+r)/2);
        T vr=query(p,q,2*k+2,(l+r)/2,r);
        return cal(vl,vr);
    }

    void eval(int k,int len){//k:0-indexed
        if(lazy[k]==opinit)return;
        node[k]=upd(node[k],rcal(lazy[k],len));
        if(k<n-1){
            lazy[2*k+1]=ecal(lazy[2*k+1],lazy[k]);
            lazy[2*k+2]=ecal(lazy[2*k+2],lazy[k]);
        }
        lazy[k]=opinit;
    }
};

using namespace std;
using ll = long long;
using pi = pair<int,int>;
int main() {
    int n,m,q;
    cin>>n>>m>>q;
    vector<pi> init(n+1);
    init[0]=pi(0,n+10);
    for(int i = 1;i <= n;++i) {
        init[i]=pi(i-1,i-1);
    }
    vector<pair<pi,pi>> event;
    for(int i = 0;i < m;++i) {
        int d,a,b;
        cin>>d>>a>>b;
        --a;--b;
        event.emplace_back(pi(d,1),pi(a,b+1));
    }
    vector<bool> ans(q,false);
    map<pair<int,pi>,int> mp;
    for(int i = 0;i < q;++i) {
        int e,s,t;
        cin>>e>>s>>t;
        --s;--t;
        event.emplace_back(pi(e,0),pi(s,t));
        mp[make_pair(e,pi(s,t))]=i;
    }
    sort(event.begin(),event.end());
    LazySegmentTree<pi,pi> st(
        n,
        [](pi a,pi b){return pi(max(a.first,b.first),min(a.second,b.second));},
        [](pi a,pi b){return b;},
        [](pi a,pi b){return pi(max(a.first,b.first),min(a.second,b.second));},
        init,
        pi(0,n+10)
    );
    for(auto t:event) {
        int d=t.first.first;
        int op=t.first.second;
        int l=t.second.first;
        int r=t.second.second;
        if(op==0) {
            auto tv = st.query(l,l+1);
            //cerr<<tv<<endl;
            ans[mp[make_pair(d,pi(l,r))]]= (tv.first>=r);
        }
        else {
            auto tv = st.query(l,l+1);
            auto mv=st.query(tv.second,r);
            //cerr<<mv.first<<" "<<mv.second<<endl;
            st.update(min(l,mv.second),r,pi(mv.first,min(l,mv.second)));
        }
    }
    for(int i = 0;i < q;++i) {
        if(ans[i])cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}


```