Formless Canvas
Description
You are given a drawing on the XY-coordinate plane consisting of $a + b$ infinitely long lines and $c$ non-overlapping rectangles. $a$ of the lines are parallel to the x-axis, and $b$ of them are parallel to the y-axis. The lines and rectangles in this drawing partition the plane into some finite number of regions.
A coloring of the drawing is an assignment of a single color to each region. A coloring is considered valid if no two adjacent regions share the same color. Two regions are adjacent if there are infinitely many points in the intersection of their borders. In other words, the regions must be next to each other, and share more than a corner.
A coloring statement is a sequence of integers $k, s_1, s_2, ..., s_k$. A coloring statement is considered valid if there exists a coloring of the drawing that uses $k$ colors, has $s_1$ regions colored using the first color, has $s_2$ regions colored using the second color, and so on.
Your task is to find the lexicographically smallest valid coloring statement.
A sequence $a_1, a_2, ..., a_n$ is lexicographically smaller than another sequence $b_1, b_2, ..., b_m$ if either $n < m$ and $a_i = b_i$ for all $1 \leq i \leq n$, or if there exists an $i$ such that $a_i < b_i$ and $a_j = b_j$ for all $j < i$.
The first line of input consists of three space-separated integers $a$, $b$, and $c$ $(1 \leq a, b, c \leq 10^5)$.
The second line of input consists of $a$ space-separated integers $y_1, y_2, ..., y_a$ $(-10^9 \leq y_i \leq 10^9)$. These values represent the y-coordinates of the lines parallel to the x-axis.
The third line of input consists of $b$ space-separated integers $x_1, x_2, ..., x_b$ $(-10^9 \leq x_i \leq 10^9)$. These values represent the x-coordinates of the lines parallel to the y-axis.
The following $c$ lines each consist of four space-separated integers $x_1, y_1, x_2, y_2$ $(-10^9 \leq x_1 < x_2 \leq 10^9, -10^9 \leq y_1 < y_2 \leq 10^9)$ describing each rectangle. $(x_1, y_1)$ are the coordinates of the bottom-left corner of the rectangle, and $(x_2, y_2)$ are the coordinates of the top-right corner.
Every rectangle has at least one horizontal and vertical line passing through it. Among any two rectangles, the intersection of their areas, including borders, is empty.
It is guaranteed that all of the x-coordinates among all objects are distinct. The same is true for all of the y-coordinates.
On the first and only line, output an integer $k$, followed by a space, followed by $k$ space-separated integers $s_1, s_2, ..., s_k$.
Input
The first line of input consists of three space-separated integers $a$, $b$, and $c$ $(1 \leq a, b, c \leq 10^5)$.
The second line of input consists of $a$ space-separated integers $y_1, y_2, ..., y_a$ $(-10^9 \leq y_i \leq 10^9)$. These values represent the y-coordinates of the lines parallel to the x-axis.
The third line of input consists of $b$ space-separated integers $x_1, x_2, ..., x_b$ $(-10^9 \leq x_i \leq 10^9)$. These values represent the x-coordinates of the lines parallel to the y-axis.
The following $c$ lines each consist of four space-separated integers $x_1, y_1, x_2, y_2$ $(-10^9 \leq x_1 < x_2 \leq 10^9, -10^9 \leq y_1 < y_2 \leq 10^9)$ describing each rectangle. $(x_1, y_1)$ are the coordinates of the bottom-left corner of the rectangle, and $(x_2, y_2)$ are the coordinates of the top-right corner.
Every rectangle has at least one horizontal and vertical line passing through it. Among any two rectangles, the intersection of their areas, including borders, is empty.
It is guaranteed that all of the x-coordinates among all objects are distinct. The same is true for all of the y-coordinates.
Output
On the first and only line, output an integer $k$, followed by a space, followed by $k$ space-separated integers $s_1, s_2, ..., s_k$.
1 1 1
0
0
-1 -1 1 1
2 2 1
-1 1
-1 1
-2 -2 2 2
2 4 4
2 8 9
Note
The first sample test case can be colored as shown in following figure:
It uses $2$ colors, has $4$ regions colored orange, and another $4$ regions colored blue. It can be proven that no fewer colors than $2$ colors can be used, and that if $2$ colors are used, any color must be used at least $4$ times.
One solution to the second sample test case looks like this:
