Description

神犇有一个n个节点的图。因为神犇是神犇，所以在T时间内一些边会出现后消失。神犇要求出每一时间段内这个图是否是二分图。这么简单的问题神犇当然会做了，于是他想考考你。

Input

输入数据的第一行是三个整数n,m,T。

第2行到第m+1行，每行4个整数u,v,start,end。第i+1行的四个整数表示第i条边连接u,v两个点，这条边在start时刻出现，在第end时刻消失。

Output

输出包含T行。在第i行中，如果第i时间段内这个图是二分图，那么输出“Yes”，否则输出“No”，不含引号。

【题解思路】

线段树分治+并查集启发式合并

与【BZOJ3237】联通块做法类似

下面介绍线段树分治：

（时间线段树）有关的题以后会补充上来的

支持修改和查询，修改只在一段时间内生效，顺序可以交换，可撤销但不可删除。 对时间建立一棵线段树。 每个修改生效的时间在线段树上对应O(logn)个区间，在这些区间插入这个修改。 dfs这棵线段树，进入一个节点时进行这上面的修改，离开时撤销。 dfs到叶子时，正好进行了这个时间点生效的所有修改。

需要维护的是每个点在联通块中的奇偶性。

【code】

#include
      
        using namespace std;#define ll long long#define ull unsigned long long#define rep(k,i,j) for(int k = i;k <= j; ++k)#define FOR(k,i,j) for(int k = i;k >= j; --k)inline int read(){    int x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1; ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();}    return x*f; }const int mxn = 1e5+5;struct pr{
    int u,v;};vector
       
         tree[mxn<<2];bool ans[mxn];inline void build(int pos,int lp,int rp,int l,int r,pr range){    if(l<=lp&&rp<=r){        tree[pos].push_back(range);        return;    }    int m = lp+rp >>1;    if(l<=m) build(pos<<1,lp,m,l,r,range);    if(r>m) build(pos<<1|1,m+1,rp,l,r,range);}int f[mxn],sz[mxn],dis[mxn];inline int getf(int x){    if(x==f[x]) return x;    return f[x] = getf(f[x]);}inline int getd(int x){    int d = 0;    while(x!=f[x])        d ^= dis[x],x = f[x];//奇数次or偶数次     return d;}inline void wor(int pos/*time*/,int l,int r){    vector
        
         opt;    int m = l+r >>1;    bool flag = 0;    int sz1 = tree[pos].size();    for(int i = 0;i < sz1; ++i){        int x = tree[pos][i].u,y = tree[pos][i].v;        int fx = getf(x),fy = getf(y);        if(fx==fy){            if(!(getd(x)^getd(y))){                flag = 1;                break;                }//没有距离         }else{            if(sz[fx]>sz[fy]) swap(fx,fy),swap(x,y);            sz[y] += sz[x];            dis[fx] ^= dis[x]^dis[y]^1;            f[fx] = fy;            opt.push_back((pr){fx,fy});        }    }    if(!flag){        if(l==r) ans[l] = true;        else wor(pos<<1,l,m),wor(pos<<1|1,m+1,r);    }    int sz2 = opt.size();    for(int i = sz2-1; i > 0; --i){        int x = opt[i].u,y = opt[i].v;        sz[y] -= sz[x];        dis[x] = 0;        f[x] = x;    }}int n,m,T;int main(){    n = read(),m = read(),T = read();    rep(i,1,m){        int u = read(),v = read();        int l = read(),r = read();        if(l