## 1) Concise abridged problem statement

You have a white rectangle canvas of size \(W \times H\). On it, \(N\) thin black rectangular **frames** are drawn (their borders only), axis-parallel. No two frames share any point (so borders do not intersect or touch).

A **facet** is any connected white region enclosed by these frames and/or the canvas boundary (i.e., connected components of the canvas after removing all frame borders).

Output the areas of all facets in **non-decreasing order**.

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

---

## 2) Detailed editorial (explaining the provided solution)

### Key observation: facets correspond to “rectangle minus children”
Because frames never intersect or touch, their nesting structure is laminar:

- Any two frames are either completely disjoint, or one is strictly inside the other (since they cannot cross).
- Therefore, if we consider each frame as a rectangle region, the set of rectangles forms a **forest** by containment.
- If we also add the whole canvas as rectangle `0`, everything becomes a single **rooted tree**:
  - Parent of a rectangle = the smallest rectangle that strictly contains it (possibly the canvas).

Now consider the white regions (facets). For any rectangle \(u\) (including the canvas), the white area “owned” by \(u\) is:

\[
\text{facet\_area}(u) = \text{area}(u) - \sum_{c \in children(u)} \text{area}(c)
\]

Why?
- Borders have zero area, so only rectangle interiors matter.
- Every point inside \(u\) is either inside one of its immediate child rectangles (then it is separated by that child’s frame), or it belongs to the “free” region of \(u\).
- Because children are disjoint and non-overlapping, subtracting their areas is valid.

So the problem reduces to:
1. Build the containment parent for each rectangle.
2. Compute these “area minus children” values for all nodes (canvas + frames).
3. Sort and print.

---

### How to build the containment tree efficiently (sweep line)

We need parents for up to 60000 rectangles, so \(O(N^2)\) is too slow.

Use a vertical sweep line moving left to right:

#### Events
For each rectangle \(v\) with normalized coordinates \((x1,y1,x2,y2)\) where \(x1<x2, y1<y2\):

Create 3 events:
- At \(x=x1\): “open” at \(y=y1\)
- At \(x=x1\): “open” at \(y=y2\)
- At \(x=x2\): “close” (encoded with y=0 in this implementation)

Sort by `(x, y)`.

#### Active structure
Maintain a map `active: y -> rect_id`.

Interpretation at current sweep x:
- For each active rectangle, its vertical sides intersect the sweep line, so it “occupies” an interval \([y1,y2]\).
- The map stores **boundary y-coordinates** of these intervals so that the owner of a y-slab can be found by looking just below a y.

Initialize with canvas boundaries:
- `active[0] = 0`
- `active[H] = 0`

#### Processing an opening
When we hit `x = x1` of rectangle `v`, we insert both its y-boundaries:
- `active[y1] = v`
- `active[y2] = v`

But before inserting, we must determine `parent[v]`.

To find parent:
- Look up `it = active.lower_bound(y1)`, then take the previous entry `--it`.
- The rectangle `below = it->second` is the one whose region contains y just below `y1` at this x, hence it is the rectangle currently enclosing `v`.

There is a subtlety handled in code:
- Sometimes the entry just below belongs to a rectangle boundary rather than its interior (corner cases at shared y-levels in the map representation).
- The code checks:
  - If `rects[below][3] == it->first` (meaning `it->first` equals the top boundary of `below`), then `below` is not actually the enclosing interior at that y; use `parent[below]` instead.
  - Otherwise, parent is `below`.

This works under the “no common points” condition; it ensures we choose the immediate enclosing rectangle.

#### Processing a closing
At `x = x2`, rectangle `v` ends; remove its two y-entries:
- erase `y1` and `y2`

Complexity:
- 3N events, each does `O(log N)` map operations → `O(N log N)`.

---

### Computing facet areas
Let `area[i]` store the facet area associated with node `i`.

Start with:
- `area[0] = W * H` (canvas)

For each rectangle `i`:
- `a = (x2-x1)*(y2-y1)`
- `area[i] += a` (it contributes its own rectangle area to its own facet computation)
- `area[parent[i]] -= a` (subtract from parent’s free space)

After all rectangles processed, `area[u]` becomes exactly:
\[
\text{area}(u) - \sum_{child} \text{area}(child)
\]
which matches facet areas.

Finally:
- Sort `area[0..N]` and print.

---

## 3) 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;
}
```

---

## 4) Python solution (same approach, with detailed comments)

```python
import sys
from bisect import bisect_left

# We'll implement the same sweep-line + map logic.
# Python doesn't have a built-in ordered map with O(log N) predecessor queries,
# so we implement it using:
# - a sorted list of keys (ys)
# - a dict mapping y -> rect_id
#
# However, maintaining a sorted list with inserts/deletes is O(N) each,
# which is too slow for N=60000 in worst case.
#
# Therefore, we should use an external balanced tree structure.
# On Codeforces, Python solutions typically use "sortedcontainers" (not allowed),
# so a practical pure-Python approach is to use PyPy + "bisect" with arrays
# only if constraints allow. Here they don't.
#
# To keep this correct and efficient in Python without external libs,
# we can use a Treap (randomized BST) to support:
# - insert(key, value)
# - erase(key)
# - lower_bound(key) and predecessor(key)
# all in expected O(log N).

import random
random.seed(0)

class TreapNode:
    __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 rotate_right(p):
    q = p.left
    p.left = q.right
    q.right = p
    return q

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

def treap_insert(root, key, val):
    """Insert or overwrite key with val."""
    if root is None:
        return TreapNode(key, val)
    if key == root.key:
        root.val = val
        return root
    if key < root.key:
        root.left = treap_insert(root.left, key, val)
        if root.left.prio > root.prio:
            root = rotate_right(root)
    else:
        root.right = treap_insert(root.right, key, val)
        if root.right.prio > root.prio:
            root = rotate_left(root)
    return root

def treap_erase(root, key):
    """Erase key if present."""
    if root is None:
        return None
    if key < root.key:
        root.left = treap_erase(root.left, key)
        return root
    if key > root.key:
        root.right = treap_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
    # both children exist: rotate the higher-priority child up
    if root.left.prio > root.right.prio:
        root = rotate_right(root)
        root.right = treap_erase(root.right, key)
    else:
        root = rotate_left(root)
        root.left = treap_erase(root.left, key)
    return root

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

def treap_predecessor(root, key):
    """Return node with largest 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

def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)

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

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

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

    # Treap stores active boundaries: key=y, val=rect_id
    root = None
    root = treap_insert(root, 0, 0)
    root = treap_insert(root, h, 0)

    parent = [0] * (n + 1)

    for x, y, v in events:
        x1, y1, x2, y2 = rects[v]

        if x == x1:
            # On the bottom boundary event compute the parent
            if y == y1:
                pred = treap_predecessor(root, y1)
                # pred must exist because we always have key=0
                below = pred.val
                below_x1, below_y1, below_x2, below_y2 = rects[below]

                # Same boundary disambiguation as C++:
                # if predecessor key equals below's top, use below's parent
                if below_y2 == pred.key:
                    parent[v] = parent[below]
                else:
                    parent[v] = below

            # Insert boundary y -> v (both y1 and y2)
            root = treap_insert(root, y, v)

        else:
            # close: remove both boundaries
            root = treap_erase(root, y1)
            root = treap_erase(root, y2)

    # Compute facet areas using add-to-self, subtract-from-parent trick
    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()
```

---

## 5) Compressed editorial

- Rectangles (frames) are non-intersecting ⇒ their interiors are either disjoint or nested ⇒ add canvas as node 0 gives a containment tree.
- Each facet corresponds to “free area” inside some node:
  \[
  facet(u)=area(u)-\sum_{c \in children(u)} area(c)
  \]
- Build parents with a vertical sweep line:
  - Events: for each rect \(i\): open at \(x1\) for \(y1,y2\), close at \(x2\).
  - Maintain ordered map `active[y]=rect_id` for current sweep.
  - When opening at \(y1\), parent is rectangle from predecessor boundary below \(y1\) (with a small boundary tie fix).
  - Insert both y-boundaries; on close erase them.
- Compute facet areas via difference:
  - `area[0]=W*H`
  - For each rect i with area a: `area[i]+=a`, `area[parent[i]]-=a`
- Sort `area[0..N]` and print. Complexity \(O(N\log N)\).