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 #include using namespace std; typedef long long ll; typedef pair pii; #define ST first #define ND second #define PB push_back const int hs = 3; struct H { vector h; H() : h(hs) {} H(vector h) : h(h) {} H operator+(H &b) { H res; for(int i=0; i < hs; i++) { res.h[i] = h[i]+b.h[i]; } return res; } H operator-(const H &b) { H res; for(int i=0; i < hs; i++) { res.h[i] = h[i]-b.h[i]; } return res; } H operator*(const H &b) { H res; for(int i=0; i < hs; i++) { res.h[i] = h[i]*b.h[i]; } return res; } H operator%(const H &b) { H res; for(int i=0; i < hs; i++) { res.h[i] = h[i]%b.h[i]; } return res; } bool operator!=(const H &b) { return h != b.h; } }; const int maxn = 500100; H base, mod; H po[maxn]; bool operator<(const H &a, const H &b) { return a.h < b.h; } void init(int n) { base = H({2, 3, 5}); mod = H({1000000007, 1000000009, 1190494759}); po[0] = H({1, 1, 1}); for(int i=1; i <= n; i++) { po[i] = (po[i-1]*base)%mod; } } ll solve(vector &a, int X) { sort(a.begin(), a.end()); vector> v; int p = 0; H h; for(int i=0; i < a.size(); i++) { int b = a[i].ST; v.PB({h, b-p}); int id = a[i].ND; if(id > 0) { h = ((h+po[id])%mod+mod)%mod; } else { // cerr << id << "\n"; h = ((h-po[-id])%mod+mod)%mod; } p = b; } v.PB({h, X-p}); sort(v.begin(), v.end()); int best = 0, current=0; for(int i=0; i < v.size(); i++) { // cerr << v[i].ND << " "; if(i == 0 || v[i-1].ST != v[i].ST) { current = v[i].ND; } else { current+= v[i].ND; } best = max(best, current); } // cerr << "\n"; // cerr << best << "\n"; return best; } int main() { ios_base::sync_with_stdio(0); int n; ll x, y; cin >> n >> x >> y; init(n); vector a, b; for(int i=0; i < n; i++) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; if(x1 > x2) { swap(x1, x2); } if(y1 > y2) { swap(y1, y2); } a.PB({x1, i+1}); a.PB({x2, -i-1}); b.PB({y1, i+1}); b.PB({y2, -i-1}); } ll res = solve(a, x)*solve(b, y); cout << res << "\n"; }