1
2
3
4
5

3 3 3
1 2 0 2
2 3 0 3
1 3 1 2

1
2
3
4

Yes
No
Yes

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112

// Problem: P5787 二分图 /【模板】线段树分治
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5787
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Author: Ybw051114
//
// Powered by CP Editor (https://cpeditor.org)

#include "ybwhead/ios.h"
const int maxn = 1e6 + 10;
struct node
{
    int a, b;
};
vector<node> q[maxn];
void add(int p, int l, int r, int ll, int rr, node d)
{
    if (l > rr || r < ll)
        return;
    if (ll <= l && r <= rr)
    {
        q[p].push_back(d);
        return;
    }
    int mid = l + r >> 1;
    if (ll <= mid)
        add(p << 1, l, mid, ll, rr, d);
    if (rr > mid)
        add(p << 1 | 1, mid + 1, r, ll, rr, d);
}
int n, m, k;
int top, s1[maxn], s2[maxn];
int f[maxn], siz[maxn];
int find(int x)
{
    if (f[x] == x)
        return x;
    return find(f[x]);
}
void merge(int x, int y)
{
    x = find(x), y = find(y);
    if (x == y)
        return;
    if (siz[x] > siz[y])
    {
        swap(x, y);
    }
    s1[++top] = x;
    s2[top] = y;
    f[x] = y;
    siz[y] += siz[x];
    return;
}
void solve(int p, int l, int r)
{
    bool flg = 1;
    int tmp = top;
    for (auto x : q[p])
    {
        int a = find(x.a);
        int b = find(x.b);
        // yout << a << " " << b << endl;
        if (a == b)
        {
            for (int k = l; k <= r; k++)
                puts("No");
            flg = 0;
            break;
        }
        merge(x.a, x.b + n);
        merge(x.a + n, x.b);
    }
    if (flg)
    {
        if (l == r)
        {
            puts("Yes");
        }
        else
        {
            int mid = l + r >> 1;
            solve(p << 1, l, mid);
            solve(p << 1 | 1, mid + 1, r);
        }
    }
    while (top > tmp)
    {
        siz[s2[top]] -= siz[s1[top]];
        f[s1[top]] = s1[top];
        top--;
    }
    return;
}
int main()
{
    yin >> n >> m >> k;
    for (int i = 1; i <= m; i++)
    {
        int l, r, a, b;
        yin >> a >> b >> l >> r;
        ++l;
        // ++r;
        node v = (node){a, b};
        add(1, 1, k, l, r, v);
    }
    for (int i = 1; i <= 2 * n; i++)
        f[i] = i, siz[i] = 1;
    solve(1, 1, k);
    return 0;
}