Histogrami
A histogram is a graphical representation of a statistical distribution of data. In other words, it is a function that assigns a positive integer value to each number in the interval $0, 1, 2, \dots , W  1$. For this task, we describe a histogram with a series of points in the standard coordinate system which, sequentially, determine the top edge of the area that the histogram encloses.
More specifically, we define a histogram of width $W$ with an even number of points in the form:
\[ (x_0, y_1), (x_1, y_1), (x_1, y_2), (x_2, y_2), (x_2, y_3), \dots ,(x_{N/21}, y_{N/2}),(x_{N/2}, y_{N/2}). \]Therefore, starting from the first point, for every pair of adjacent points it must hold that their $y$ coordinates are equal and that their $x$ coordinates are equal. Thus, the histogram begins and ends with a horizontal segment and in between horizontal and vertical segments alternate.
Additionally, the following holds for the shape of a histogram:

$x_0 = 0$ – the histogram begins on the line $x = 0$.

$x_{N/2} = W$ – the histogram ends on the line $x = W$.

$x_ i < x_{i+1}$, for each $i = 1, 2, \dots , N/2  1$  the histogram is defined from left to right and the length of each horizontal segment is at least one.

$y_ i > 0$ – the height of the histogram is always greater than zero.

$y_ i \not= y_{i+1}$ – the length of each vertical segment is at least one.
For a histogram $H$, let $y_ H(x)$ be the height of the histogram in the interval $\left\langle x, x+1 \right\rangle $. For example, the surface area which the histogram encloses can be calculated by formula $\sum ^{W1}_{x=0} y_ H(x)$. If two histograms, $H$ and $H’$, are given, with equal width $W$ (which can possibly be defined with a different number of points), then we can measure the difference between these two histograms in various ways. This measure of difference between two histograms is also called inaccuracy of histogram $H’$ with regard to histogram $H$. In this task, we examine two different ways of measuring differences between two histograms and we define them in the following way:
\begin{align*} \operatorname {diffcount}(H’, H) & = \sum ^{W1}_{x=0} \operatorname {diff}(y_ H(x), y_{H'}(x)), \text {where $\operatorname {diff}(y_1, y_2) = 0$ if $y_1 = y_2$ and $1$ otherwise.} \\ \operatorname {abserror}(H’, H) & = \sum ^{W1}_{x=0} y_ H(x)  y_{H'}(x) \end{align*}In other words, the first way measures the number of unit segments $\left\langle x, x + 1 \right\rangle $ in which the two histograms differ, whereas the second way is the sum of absolute values of differences on those individual unit segments.
Write a program that will, for a given histogram $H$, set of points $S$ and way of measuring inaccuracy, find and output histogram $H’$ which only uses points from the set $S$ in its definition and has the least possible inaccuracy with regard to the given histogram $H$.
The definition of histogram $H’$ must comply with all aforementioned conditions (for example, there shouldn’t be two continuous horizontal segments in the definition of histogram $H’$) and each point in the definition must be one of the points from the set $S$.
Input
The first line of input contains integers $N, M, G$ ($2 \le N, M \le 100\, 000$, $1 \le G \le 2$, N even), respectively: the total number of points in the definition of histogram $H$, number of points in set $S$ and the number which determines what method of measuring the inaccuracy is used: $G=1$ for diffcount and $G=2$ for abserror.
Each of the following $N$ lines contains integers $X$ and $Y$ ($0 \le X \le 10^6$, $1 \le Y \le 10^6$) – coordinates of one point from the definition of histogram $H$. The histogram’s definition will comply to all the conditions from the task statement.
Each of the following $M$ lines contains integers $X$ and $Y$ ($0 \le X \le 10^6$, $1 \le Y \le 10^6$) – coordinates of one point from set $S$. All the points in the set $S$ will be different from one another, but they can match with points from the definition of the histogram $H$.
Output
The first line of output must contain the least possible inaccuracy $D$. The second line of output must contain an even integer $L$ – the total number of points in the definition of the required optimal histogram. In each of the following $L$ lines, output two integers $X$ and $Y$ – coordinates of the point in the histogram’s definition.
The histogram’s definition must comply to all the conditions from the task.
Please note: The solution may not be unique, but the input data will be such that there is always at least one solution.
Sample Input 1  Sample Output 1 

10 12 1 0 2 2 2 2 3 4 3 4 1 5 1 5 5 9 5 9 2 10 2 0 4 0 6 3 3 3 6 9 4 9 1 5 3 5 5 10 5 9 2 10 1 8 5 
5 6 0 6 3 6 3 3 5 3 5 5 10 5 
Sample Input 2  Sample Output 2 

10 12 2 0 2 2 2 2 3 4 3 4 1 5 1 5 5 9 5 9 2 10 2 0 4 0 6 3 3 3 6 9 4 9 1 5 3 5 5 10 5 9 2 10 1 8 5 
14 4 0 4 9 4 9 1 10 1 