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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int tree[8100005];
bool blocked[8100005];

void block(int pos, int s, int e, int cs, int ce){
    if (blocked[pos]){
        return;
    }
    else if ((s == cs) && (e == ce)){
        blocked[pos] = true;
        tree[pos] = 0;
        return;
    }
    else if ((s <= (cs + ce)/2) && (e <= (cs + ce)/2)){
        block(pos * 2, s, e, cs, (cs + ce)/2);
    }
    else if ((s > (cs + ce)/2) && (e > (cs + ce)/2)){
        block(pos * 2 + 1, s, e, (cs + ce)/2 + 1, ce);
    }
    else {
        block(pos * 2, s, (cs + ce)/2, cs, (cs + ce)/2);
        block(pos * 2 + 1, (cs + ce)/2 + 1, e, (cs + ce)/2 + 1, ce);
    }
    //printf("bl %d %d %d %d %d %d %d\n", pos, s, e, tree[pos], tree[pos * 2], tree[pos * 2 + 1], blocked[pos]);
    tree[pos] = tree[pos * 2] + tree[pos * 2 + 1];
}

void add(int pos, int s, int cs, int ce, int v){
    if ((s == cs) && (s == ce)){
        tree[pos] = v;
        return;
    }
    else if (s <= (cs + ce)/2){
        add(pos * 2, s, cs, (cs + ce)/2, v);
    }
    else {
        add(pos * 2 + 1, s, (cs + ce)/2 + 1, ce, v);
    }
    tree[pos] = tree[pos * 2] + tree[pos * 2 + 1];
}

long long get(int pos, int s, int e, int cs, int ce){
    //printf("gg %d %d %d %d %d %d %d\n", pos, s, e, cs, ce, tree[pos], blocked[pos]);
    if (blocked[pos]){
        return 0;
    }
    else if ((s == cs) && (e == ce)){
        return tree[pos];
    }
    else if ((s <= (cs + ce)/2) && (e <= (cs + ce)/2)){
        return get(pos * 2, s, e, cs, (cs + ce)/2);
    }
    else if ((s > (cs + ce) / 2) && (e > (cs + ce)/2)){
        return get(pos * 2 + 1, s, e, (cs + ce)/2 + 1, ce);
    }
    else {
        return get(pos * 2, s, (cs + ce)/2, cs, (cs + ce)/2) + get(pos * 2 + 1, (cs + ce)/2 + 1, e, (cs + ce)/2 + 1, ce);
    }
}

int n, Z[2];
std::vector<std::pair<int,int>> v, w[2];
std::vector<int> q, _q;
std::set<std::pair<int,int>> l, r;

int find(int a){
    int e = 0, f = q.size() - 1;
    while (e <= f){
        int mid = (e + f)/2;
        if (a == q[mid]){
            return mid;
        }
        else if (a < q[mid]){
            f = mid - 1;
        }
        else {
            e = mid + 1;
        }
    }
    return -1;
}

int main(){
    scanf("%d%d%d", &n, &Z[0], &Z[1]);
    for (int i = 0; i < n; i++){
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        if (a > c){
            std::swap(a, c);
        }
        if (b > d){
            std::swap(b, d);
        }
        w[0].push_back(make_pair(a, c));
        w[1].push_back(make_pair(b, d));
    }
    //printf("A1\n");
    long long b[] = {0, 0};
    for (int t = 0; t < 2; t++){
        for (int i = 0; i < n; i++){
            v.push_back(make_pair(w[t][i].first, i));
        }
        _q.push_back(0);
        _q.push_back(Z[t]);
        for (auto& el : w[t]){
            _q.push_back(el.first);
            _q.push_back(el.second);
        }
        std::sort(_q.begin(), _q.end());
        q.push_back(_q[0]);
        for (int i = 1; i < (int)_q.size(); i++){
            if (_q[i] > q[q.size() - 1]){
                q.push_back(_q[i]);
            }
        }
        for (int i = 0; i < q.size() - 1; i++){
            add(1, 2 * i + 2, 1, 2 * q.size() - 1, q[i + 1] - q[i]);
        }
        //printf("B1\n");
        std::sort(v.begin(), v.end());
        for (int i = 0; i < v.size(); i++){
            int bst = 1000000000;
            //printf("Z1 %d\n", i);
            while (!r.empty()){
                auto f = *r.begin();
                if (f.first <= v[i].first){
                    r.erase(r.begin());
                    l.erase(std::make_pair(w[t][f.second].first, f.second));
                    //printf("WW1 %d %d %d %d %d %d %d %d\n", find(w[t][f.second].first) * 2 + 1, find(f.first) * 2 + 1, r.begin()->first, r.begin()->second, f.first, f.second, w[t][f.second].first, f.second);
                    block(1, find(w[t][f.second].first) * 2 + 1, find(f.first) * 2 + 1, 1, q.size() * 2 - 1);
                    if ((!r.empty()) && (r.begin()->first <= v[i].first)){
                        //printf("hohopp %lld %lld %d %d %d %d\n", b[t], get(1, find(f.first) * 2 + 1, find(r.begin()->first) * 2 + 1, 1, q.size() * 2 - 1), find(f.first) * 2 + 1, find(r.begin()->first) * 2 + 1, f.first, r.begin()->first);
                        if (l.size() > 0){
                            b[t] = std::max(b[t], get(1, find((--l.end())->first) * 2 + 1, /*find(f.first) * 2 + 1,*/ find(r.begin()->first) * 2 + 1, 1, q.size() * 2 - 1));
                        }
                        else {
                            b[t] = std::max(b[t], get(1, 1, find(r.begin()->first) * 2 + 1, 1, q.size() * 2 - 1));
                        }
                    }
                }
                else {
                    break;
                }
            }
            //printf("bum\n");
            if (l.size() > 0){
                //printf("hoho %lld %lld %d %d\n", b[t], get(1,  find((--l.end())->first) * 2 + 1, find(v[i].first) * 2 + 1, 1, q.size() * 2 - 1), find(v[i - 1].first) * 2 + 1, find(v[i].first) * 2 + 1);
                b[t] = std::max(b[t], get(1, find((--l.end())->first) * 2 + 1, find(v[i].first) * 2 + 1, 1, q.size() * 2 - 1));
                if (t == 1){
                    //printf("checkout ---------- %lld %d %d %d\n", get(1, 7, 7, 1, q.size() * 2 - 1), 5, 7, 0);
                }
            }
            else {
                //printf("what? %d\n", v[i].first);
                b[t] = std::max(b[t], get(1, 1, find(v[i].first) * 2 + 1, 1, q.size() * 2 - 1));
            }
            //printf("W2 %d %d %lld\n", i, v[i].first, b[t]);
            l.insert(v[i]);
            r.insert(std::make_pair(w[t][v[i].second].second, v[i].second));
            if (i < v.size() - 1){
                bst = std::min(bst, v[i + 1].first);
            }
            if (!r.empty()){
                bst = std::min(bst, r.begin()->first);
            }
            b[t] = std::max(b[t], (long long)bst - v[i].first);
            //printf("W1 %lld %d %d %d\n", b[t], bst, i == 1 ? r.begin()->first : 0, v[i].first);
        }
        //printf("B2 %d %d\n", (int)l.size(), (int)r.size());
        //int co = 0;
        while (!r.empty()){
            //printf("C1\n");
            auto last = *(--l.end());
            auto f = *r.begin();
            //printf("C2 %d %d %d\n", find(last.first) * 2 + 1, find(f.first) * 2 + 1, f.first);
            /*for (int i = 0; i < q.size(); i++){
                printf("%d ", q[i]);
            }
            printf("\n");*/
            b[t] = std::max(b[t], get(1, find(last.first) * 2 + 1, find(f.first) * 2 + 1, 1, q.size() * 2 - 1));
            //printf("C3 %lld %d %d %d\n", b[t], tree[1], tree[2], tree[3]);
            r.erase(r.begin());
            l.erase(std::make_pair(w[t][f.second].first, f.second));
            //printf("C4 %d %d\n", find(w[t][f.second].first) * 2 + 1, find(f.first) * 2 + 1);
            block(1, find(w[t][f.second].first) * 2 + 1, find(f.first) * 2 + 1, 1, q.size() * 2 - 1);
            //printf("C5\n");
            //co++;
        }
        b[t] = std::max(b[t], get(1, 1, q.size() * 2 - 1, 1, q.size() * 2 - 1));
        /*if (t == 1){
            printf("------\n");
            printf("checkout ---------- %lld\n", get(1, find(2), find(3), 1, q.size() * 2 - 1));
        }*/
        //printf("CC %lld %d %d %d %d %d %d\n", b[t], tree[1], tree[2], tree[3], blocked[1], blocked[2], blocked[3]);
        for (int i = 0; i < 16 * (n + 3); i++){
            tree[i] = 0;
            blocked[i] = false;
        }
        v.clear();
        q.clear();
        _q.clear();
        l.clear();
        r.clear();
    }
    printf("%lld\n", b[0] * b[1]);
}