물리

안드로이드 바샤는 『가장 어린 아이들을 위한 재미있는 물리』라는 책을 읽고 있다. 최근 그는 등가속도 운동을 다룬 장을 읽고 직접 실험해 보기로 했다. 이를 위해 바샤는 리모컨으로 가속도를 다르게 줄 수 있는 기계 거북이를 만들었다.

바샤는 거북이를 로비에 내보내며 가속도를 여러 번 바꾸었다. 구간별 선형 속도 함수 $v_1(t)$의 그래프를 그린 뒤 실험을 한 번 더 했다. 이번에는 구간별 선형이면서 연속인 속도 함수 $v_2(t)$를 얻었고, 이 함수의 그래프도 그렸다.

세 번째 시도 전에 바샤는 $v_1(t)$와 $v_2(t)$를 한 그래프에 그린 것이 잘못이었다는 것을 깨달았다. 그 때문에 어떤 선분이 어느 함수에 속하는지 알 수 없게 되었다. 두 실험은 모두 시간 $T$ 동안 진행되었고, 두 번 모두 거북이는 로비 길이와 같은 거리를 이동했다. 이 조건을 이용해 두 그래프를 복원하도록 바샤를 도와주자.

첫 줄에는 각 실험의 지속 시간 $T$가 주어진다 ($2 \le T \le 10^6$). 이어서 $h(t) = \max(v_1(t), v_2(t))$와 $g(t) = \min(v_1(t), v_2(t))$를 설명하는 정보가 주어진다. 두 번째 줄에는 함수 $h(t)$의 꺾임점 개수 $n$이 주어진다. 다음 $n$개 줄에는 $h(t)$의 꺾임점인 정수 쌍 $t_i$와 $h(t_i)$가 주어진다 ($0 = t_1 < t_2 < \dots < t_{n-1} < t_n = T$, $0 \le h(t_i) \le 10^6$). 연속한 세 꺾임점은 한 직선 위에 있지 않다. 그 다음 줄부터는 같은 형식으로 $g(t)$가 주어진다. 모든 $x \in [0; T]$에 대해 $g(t) \le h(t)$이며, $g(t) = h(t)$인 점은 30개를 넘지 않는다 (특히 두 그래프는 공통 선분을 갖지 않는다). 각 함수의 꺾임점 개수는 2개 이상 100000개 이하이다.

입력과 같은 형식으로 함수 $v_1(t)$와 $v_2(t)$를 출력한다. 연속한 세 꺾임점이 한 직선 위에 있으면 안 된다. 출력의 모든 수는 정수여야 한다. 답이 여러 개이면 그중 아무거나 출력한다. 해가 적어도 하나 존재함이 보장된다.