Rectilinear Regions

A rectilinear path joining two points in the plane is a path made only of horizontal and vertical segments. A rectilinear path is monotone with respect to the $x$ axis (respectively, the $y$ axis) if its intersection with every vertical line (respectively, every horizontal line) is either empty or one contiguous piece of that line. A rectilinear path that is monotone with respect to both the $x$ axis and the $y$ axis is a staircase. A staircase is unbounded if both of its ends are semi-infinite horizontal segments, that is, the left end runs to infinity in the negative $x$ direction and the right end runs to infinity in the positive $x$ direction. A staircase is increasing or decreasing depending on whether its $y$ coordinate grows or shrinks as you walk along it from left to right. A staircase with $n$ vertical segments is called an $n$ step staircase.

Two unbounded staircases $L$ and $U$ can bound several closed rectilinear regions, or none at all. Some of those regions are bounded below by $L$ and above by $U$. In Figure G.1 the two regions colored yellow are of that kind. This problem asks for the number of such regions and their total area. A part that stretches to infinity on one side is not a closed region, so it is not counted.

Figure G.1. An example where staircase $U$ has 3 steps and staircase $L$ has 4 steps. The two yellow regions are closed rectilinear regions bounded below by $L$ and above by $U$. The values $x_i^L, y_i^L$ (respectively $x_i^U, y_i^U$) are the $x$ and $y$ coordinates of the corner points of staircase $L$ (respectively $U$).

A staircase is written with the notation

$y_0\ x_1\ y_1\ x_2\ y_2\ \dots\ x_n\ y_n \qquad (1)$

where $x_1 < x_2 < \dots < x_n$ are the $x$ coordinates of the vertical segments and $y_0, y_1, \dots, y_n$ are the $y$ coordinates of the horizontal segments. An increasing staircase has $y_0 < y_1 < \dots < y_n$ and a decreasing staircase has $y_0 > y_1 > \dots > y_n$. Here $y_0$ is the height of the left semi-infinite horizontal segment and $y_n$ is the height of the right one.

All $x$ coordinates of the corner points of $L$ and $U$ that appear in notation (1) are distinct, and all $y$ coordinates of those corner points are distinct as well. Given the two unbounded staircases $L$ and $U$, compute the number of closed rectilinear regions bounded below by $L$ and above by $U$, together with their total area.

The first line contains two positive integers $n$ and $m$, the number of steps of the unbounded staircases $L$ and $U$. ($1 \le n \le 25000$, $1 \le m \le 25000$)

The second line contains $2n+1$ integers describing the corner points of staircase $L$, and the third line contains $2m+1$ integers describing the corner points of staircase $U$, both in the order of notation (1). Every coordinate is a non-negative integer at most $50000$.

Print two integers $k$ and $w$ on one line, separated by a space. Here $k$ is the number of closed rectilinear regions bounded below by staircase $L$ and above by staircase $U$, and $w$ is their total area. If there is no such region, print 0 for both $k$ and $w$.