히스토그램

히스토그램은 데이터 분포를 나타내는 그래프다. 이 문제에서는 너비 $W$인 히스토그램을 좌표평면의 점들로 표현한다. 점은 짝수 개이며

$(x_0, y_1),(x_1, y_1),(x_1, y_2),(x_2, y_2),\ldots,(x_{N/2-1}, y_{N/2}),(x_{N/2}, y_{N/2})$

형태를 따른다. 인접한 두 점은 $x$좌표가 같거나 $y$좌표가 같고, 가로와 세로 변이 번갈아 나온다.

조건은 다음과 같다.

1. $x_0 = 0$
2. $x_{N/2} = W$
3. $x_i < x_{i+1}$
4. $y_i > 0$
5. $y_i \ne y_{i+1}$

히스토그램 $H$에 대해 구간 $\langle x, x+1 \rangle$에서의 높이를 $y_H(x)$라 한다. 두 히스토그램 $H$와 $H'$의 오차는 다음 두 방식 중 하나로 잰다.

$\text{diffcount}(H', H) = \sum_{x=0}^{W-1} \text{diff}(y_H(x), y_{H'}(x)),\quad \text{diff}(y_1,y_2)=0\text{ if }y_1=y_2\text{ else }1$

$\text{abserror}(H', H) = \sum_{x=0}^{W-1} |y_H(x) - y_{H'}(x)|$

주어진 히스토그램 $H$, 점 집합 $S$, 오차 측정 방식이 주어질 때, 정의에 쓰는 모든 점이 $S$에 속하는 히스토그램 $H'$ 중 $H$와의 오차가 최소인 것을 찾아 출력하라.

첫 줄에 $N, M, G$ ($2 \le N \le 100000$, $N$은 짝수, $2 \le M \le 100000$, $1 \le G \le 2$)가 주어진다. $G=1$이면 diffcount, $G=2$이면 abserror를 쓴다.

다음 $N$줄: 히스토그램 $H$를 정의하는 점 $(X, Y)$.

다음 $M$줄: 집합 $S$의 점 $(X, Y)$. ($0 \le X \le 10^6$, $1 \le Y \le 10^6$)

첫 줄에 최소 오차 $D$.

둘째 줄에 최적 히스토그램을 정의하는 짝수 개수 $L$.

다음 $L$줄에 점 좌표 $X\ Y$를 출력한다. 정의는 문제의 모든 조건을 만족해야 한다.