<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

319. Kalevich Strikes Back
Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



And yet again the Berland community can see that talent is always multi-sided. The talent is always seeking new ways of self-expression. This time genius Kalevich amazed everybody with his new painting "Rectangular Frames". The masterpiece is full of impenetrable meaning and hidden themes.

Narrow black rectangular frames are drawn on a white rectangular canvas. No two frames have a common point. Sides of each frame are parallel to the sides of the canvas.

The painting is very big and the reduced replica cannot pass the idea of the original drawing. That's why Kalevich requested that the simplified versions of the masterpiece should be used as replicas. The simplified version is the sequence of the areas of all facets of the original. A facet is a connected enclosed white area within the painting. The areas in the sequence should be written in the non-decreasing order.

Input
The first line of the input contains an integer N (1 ≤ N ≤ 60000) — the number of the frames on the drawing. The second line contains integer numbers W and H (1 ≤ W, H ≤ 108).

Let's introduce the Cartesian coordinate system in such a way that the left bottom corner of the canvas has (0, 0) coordinate and the right top corner has the (W, H) coordinate. The sides of the canvas are parallel to the axes.

The following N lines contain the description of the frames. Each description is composed of the coordinates of the two opposite corners of the corresponding frame x1, y1, x2, y2 (1 ≤ x1, x2 < W; 1 ≤ y1, y2 < H; x1 != x2, y1 != y2). All coordinates are integers. No two frames have a common point.

Output
Write the desired sequence to the output.

Example(s)
sample input
sample output
1
3 3
2 1 1 2
1 8

<|response|>
## 1) Abridged problem statement (concise)

Given a white canvas rectangle of size \(W \times H\) and \(N\) thin black axis-aligned rectangular **frames** (only borders, zero thickness). No two frames share any point (they don’t intersect or touch).

A **facet** is a connected white region remaining after removing all frame borders. Output the **areas of all facets** in **non-decreasing order**.

Constraints: \(1 \le N \le 60000\), \(W,H \le 10^8\).

---

## 2) Key observations

1. **No intersections ⇒ laminar (nested/disjoint) structure**  
   Since frames don’t intersect or touch, any two rectangles are either:
   - completely disjoint, or
   - one strictly inside the other.  
   So the set of rectangles forms a **forest by containment**.

2. **Add the canvas as a “rectangle 0” root ⇒ containment tree**  
   Let rectangle 0 be the whole canvas \((0,0)-(W,H)\). Then every frame has a unique smallest containing rectangle (possibly the canvas), so we get a rooted tree.

3. **Facet areas are “area minus children areas”**  
   Borders have zero area, so only rectangle interiors matter.  
   For each node \(u\) (canvas or a frame):
   \[
   \text{facet}(u) = \text{area}(u) - \sum_{c \in children(u)} \text{area}(c)
   \]
   Children are disjoint, so subtraction is valid.

4. **We only need each rectangle’s parent**  
   Once we know `parent[i]`, we can compute all facet areas using a simple difference accumulation:
   - `facet[0] = W*H`
   - for each rectangle \(i\) of area \(a\):
     - `facet[i] += a`
     - `facet[parent[i]] -= a`

5. **Parent can be found in \(O(\log N)\) with a sweep line + ordered map**  
   Sweep vertical line from left to right, maintain active rectangles using a map keyed by certain y-boundaries. For a rectangle opening at its left side, a predecessor query at \(y_1\) identifies the immediate container.

---

## 3) Full solution approach

### Step A — Normalize rectangles
For each input \((x_1,y_1,x_2,y_2)\), swap so that:
- \(x_1 < x_2\), \(y_1 < y_2\)

Store canvas as rectangle `0: (0,0)-(W,H)`.

---

### Step B — Build containment parents with a sweep line

**Events**  
For each rectangle \(i\) (1..N), create 3 events:
- open boundary at \((x_1, y_1)\)
- open boundary at \((x_1, y_2)\)
- close at \((x_2, 0)\) (y is just a tie-breaker)

Sort events by `(x, y)`.

**Active structure**  
Maintain an ordered map:
- `active[y] = rect_id`

Initialize:
- `active[0] = 0`
- `active[H] = 0`

This map encodes which rectangle “owns” the vertical strip at the current sweep x.

**Processing**
- If event is an **opening** (x == rectangle’s x1):
  - When handling the bottom boundary event (y == y1), compute parent:
    - find predecessor key just below `y1` using `lower_bound(y1)` then `--it`
    - candidate = `it->second`
    - subtle boundary fix: if `it->first` equals candidate’s `y2` (top boundary), then the true container is `parent[candidate]` (because we are on a boundary, not inside).
  - insert `active[y] = i` (for both y1 and y2)
- If event is a **closing** (x == x2):
  - erase keys `y1` and `y2`

Complexity: \(O(N \log N)\).

---

### Step C — Compute facet areas
Create array `ans[0..N]` (64-bit).
- `ans[0] = W*H`
- For each rectangle \(i\):
  - \(a = (x_2-x_1)(y_2-y_1)\)
  - `ans[i] += a`
  - `ans[parent[i]] -= a`

Now `ans[u]` equals the facet area associated with node `u`.  
Sort `ans` and print.

---

## 4) C++ Solution

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

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, w, h;
vector<array<int, 4>> rects;

void read() {
    cin >> n >> w >> h;
    rects.resize(n + 1);
    rects[0] = {0, 0, w, h};
    for(int i = 1; i <= n; i++) {
        auto& r = rects[i];
        cin >> r[0] >> r[1] >> r[2] >> r[3];
        if(r[0] > r[2]) {
            swap(r[0], r[2]);
        }
        if(r[1] > r[3]) {
            swap(r[1], r[3]);
        }
    }
}

void solve() {
    // The problem has a slightly convoluted problem statement, but essentially
    // says that we have a large canvas with n rectangles that don't intersect
    // but can cover each other, and asks us to find the "empty" areas. The
    // structure of the rectangles is essentially a tree, so if we treat the
    // canvas as a separate rectangle with coordinates (0,0) and (W,H), we can
    // simply extract area(u) - SUM_{c child of u} area(c). The only question
    // left is how to build this tree. There is a fairly straight forward way
    // with a sweep-line approach:
    //
    // We sweep a vertical line left to right. For each rectangle we create 3
    // events sorted by x: two "open" events at x1 (for y1 and y3) and one
    // "close" event at x2. We maintain a map from y-coordinate to rectangle-id
    // representing which rectangle "owns" each y-interval at the current sweep
    // position. The canvas boundaries y=0 and y=H map to rectangle 0.
    //
    // When we open rectangle v (hit x1), we first query the map for the entry
    // just below y1 — that rectangle is v's parent. Then we insert y1->v and
    // y3->v into the map. When we close rectangle v (hit x2), we remove both
    // entries. Since rectangles don't touch or overlap, this correctly finds
    // the immediate enclosing rectangle for each frame.

    struct event {
        int x, y, id;
        bool operator<(const event& o) const {
            return x < o.x || (x == o.x && y < o.y);
        }
    };

    vector<event> events;
    for(int i = 1; i <= n; i++) {
        events.push_back({rects[i][0], rects[i][1], i});
        events.push_back({rects[i][0], rects[i][3], i});
        events.push_back({rects[i][2], 0, i});
    }
    sort(events.begin(), events.end());

    map<int, int> active;
    active[0] = 0;
    active[h] = 0;

    vector<int> parent(n + 1, 0);

    for(int i = 0; i < (int)events.size(); i++) {
        int x = events[i].x, y = events[i].y, v = events[i].id;
        if(x == rects[v][0]) {
            if(y == rects[v][1]) {
                auto it = active.lower_bound(y);
                --it;
                int below = it->second;
                if(rects[below][3] == it->first) {
                    parent[v] = parent[below];
                } else {
                    parent[v] = below;
                }
            }
            active[y] = v;
        } else {
            active.erase(rects[v][1]);
            active.erase(rects[v][3]);
        }
    }

    vector<int64_t> area(n + 1, 0);
    area[0] = (int64_t)w * h;
    for(int i = 1; i <= n; i++) {
        int64_t a =
            (int64_t)(rects[i][2] - rects[i][0]) * (rects[i][3] - rects[i][1]);
        area[i] += a;
        area[parent[i]] -= a;
    }

    sort(area.begin(), area.end());
    for(int i = 0; i <= n; i++) {
        cout << area[i];
        if(i < n) {
            cout << ' ';
        }
    }
    cout << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

Python lacks a built-in ordered map with \(O(\log N)\) predecessor queries, so we implement a **Treap** (randomized BST) to support:
- insert / erase
- predecessor (largest key < y)
in expected \(O(\log N)\).

```python
import sys
import random

# ---------------- Treap (randomized balanced BST) ----------------

random.seed(0)

class Node:
    __slots__ = ("key", "val", "prio", "left", "right")
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.prio = random.randint(1, 1 << 30)
        self.left = None
        self.right = None

def rot_right(p):
    q = p.left
    p.left = q.right
    q.right = p
    return q

def rot_left(p):
    q = p.right
    p.right = q.left
    q.left = p
    return q

def insert(root, key, val):
    """Insert key->val (overwrite if key exists)."""
    if root is None:
        return Node(key, val)
    if key == root.key:
        root.val = val
        return root
    if key < root.key:
        root.left = insert(root.left, key, val)
        if root.left.prio > root.prio:
            root = rot_right(root)
    else:
        root.right = insert(root.right, key, val)
        if root.right.prio > root.prio:
            root = rot_left(root)
    return root

def erase(root, key):
    """Erase key if exists."""
    if root is None:
        return None
    if key < root.key:
        root.left = erase(root.left, key)
        return root
    if key > root.key:
        root.right = erase(root.right, key)
        return root

    # key == root.key: remove this node by rotating it down
    if root.left is None:
        return root.right
    if root.right is None:
        return root.left
    if root.left.prio > root.right.prio:
        root = rot_right(root)
        root.right = erase(root.right, key)
    else:
        root = rot_left(root)
        root.left = erase(root.left, key)
    return root

def predecessor(root, key):
    """Return node with maximum node.key < key (or None)."""
    cur = root
    ans = None
    while cur is not None:
        if cur.key < key:
            ans = cur
            cur = cur.right
        else:
            cur = cur.left
    return ans

# ---------------- Solution ----------------

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    n = next(it)
    w = next(it)
    h = next(it)

    # rects[i] = (x1,y1,x2,y2), rects[0] is canvas
    rects = [(0, 0, w, h)]
    for _ in range(n):
        x1 = next(it); y1 = next(it); x2 = next(it); y2 = next(it)
        if x1 > x2: x1, x2 = x2, x1
        if y1 > y2: y1, y2 = y2, y1
        rects.append((x1, y1, x2, y2))

    # events: (x, y, id)
    events = []
    for i in range(1, n + 1):
        x1, y1, x2, y2 = rects[i]
        events.append((x1, y1, i))  # open y1
        events.append((x1, y2, i))  # open y2
        events.append((x2, 0, i))   # close
    events.sort()

    # Treap stores active boundaries y -> rect_id
    root = None
    root = insert(root, 0, 0)
    root = insert(root, h, 0)

    parent = [0] * (n + 1)

    for x, y, v in events:
        x1, y1, x2, y2 = rects[v]
        if x == x1:
            # opening: compute parent only on the bottom boundary event
            if y == y1:
                pred = predecessor(root, y1)  # must exist due to y=0
                below = pred.val
                bx1, by1, bx2, by2 = rects[below]
                # boundary disambiguation (same as C++ logic)
                if by2 == pred.key:
                    parent[v] = parent[below]
                else:
                    parent[v] = below

            root = insert(root, y, v)  # insert boundary
        else:
            # closing: remove both boundaries
            root = erase(root, y1)
            root = erase(root, y2)

    # facet areas by difference accumulation
    area = [0] * (n + 1)
    area[0] = w * h
    for i in range(1, n + 1):
        x1, y1, x2, y2 = rects[i]
        a = (x2 - x1) * (y2 - y1)
        area[i] += a
        area[parent[i]] -= a

    area.sort()
    sys.stdout.write(" ".join(map(str, area)) + "\n")

if __name__ == "__main__":
    main()
```

---

If you want, I can also add a small diagram-style explanation of why the sweep-line `active[y]` representation correctly identifies the immediate containing rectangle (the only tricky part of the solution).