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'~, 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:

~\text{diffcount}(H', H) = \sum_{x=0}^{W-1} \text{diff}(y_H(x), y_{H'}(x))~, where ~\text{diff}(y_1, y_2) = \begin{cases}0 & \text{if }y_1 = y_2 \\ 1 & \text{if }y_1 \ne y_2\end{cases}~

$$\displaystyle \text{abserror}(H', H) = \sum_{x=0}^{W-1} |y_H(x) - y_{H'}(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'~ 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'~ 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 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 5\,000~
2	25	~G = 1~
3	25	~G = 2~, ~M \le 5\,000~
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\%~ 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