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:

$${\displaystyle (x_0,y_1),(x_1,y_1),(x_1,y_2),(x_2,y_2),(x_2,y_3),\dots ,(x_{N/2-1},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:

1. $x_0=0$ - the histogram begins on the line $x=0$.
2. $x_{N/2}=W$ - the histogram ends on the line $x=W$.
3. $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.
4. $y_i>0$ - the height of the histogram is always greater than zero.
5. $y_i\ne 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 $[x,x+1]$. For example, the surface area which the histogram encloses can be calculated by the formula $\sum _{x=0}^{W-1}{y}_H(x)$. If two histograms, $H$ and $H^{\prime }$, 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^{\prime }$ 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:

$\text{diffcount}(H^{\prime },H)=\sum _{x=0}^{W-1}\text{diff}(y_H(x),y_{H^{\prime }}(x))$, where $\text{diff}(y_1,y_2)=\{\begin{array}{ll}0& \text{if }{y}_1=y_2\\ 1& \text{if }{y}_1\ne y_2\end{array}$

$${\displaystyle \text{abserror}(H^{\prime },H)=\sum _{x=0}^{W-1}|y_H(x)-y_{H^{\prime }}(x)|}$$

In other words, the first way measures the number of unit segments $[x,x+1]$ 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^{\prime }$ which only uses points from the set $S$ in its definition and has the least possible inaccuracy with regard to the given histogram $H$.

Figure 1. Illustration of the histogram and the set $S$ in both test cases given below and the solutions for the first and the second way of measuring inaccuracy.

The definition of histogram $H^{\prime }$ must comply with all aforementioned conditions (for example, there shouldn't be two continuous horizontal segments in the definition of histogram $H^{\prime }$), and each point in the definition must be one of the points from the set $S$.

Input Specification

The first line of input contains integers $N,M,G$ $(2\le N,M\le {10}^5,1\le G\le 2,N$ even$)$: 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: $1$ for $\text{diffcount}$ and $2$ for $\text{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 with 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 Specification

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 with 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.

Constraints

Subtask	Points	Constraints
1	25	$G=1$, $M\le 5000$
2	25	$G=1$
3	25	$G=2$, $M\le 5000$
4	25	$G=2$

Scoring

If the histogram's definition is incorrect or wasn't output, but the first line of output is correct (minimal inaccuracy), your solution will get $70\mathrm{\%}$ of total points for that test case.

Sample Input 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

Sample Output 1

5
6
0 6
3 6
3 3
5 3
5 5
10 5

Sample Input 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

Sample Output 2

14
4
0 4
9 4
9 1
10 1