Physics

Android Vasya reads the book Amusing physics for the smallest children. Recently he read a chapter about uniformly accelerated motion and decided to set up some experiments. For this purpose, Vasya made a mechanical turtle that can be given a different acceleration by remote control.

Vasya launched his turtle into the lobby and changed its acceleration several times. After plotting the piecewise linear velocity function $v_1(t)$, he repeated the experiment. This time he got a piecewise linear continuous function $v_2(t)$ and plotted its graph too.

Before the third try, Vasya realized that plotting $v_1(t)$ and $v_2(t)$ on the same graph was a mistake. Now it is unclear which segments belong to which function. Help Vasya restore the graphs. Both experiments lasted the same time $T$, and in both runs the turtle covered the same distance, which is the length of the lobby.

The first line contains an integer $T$, the duration of each experiment ($2 \le T \le 10^6$). Then the description of the functions $h(t) = \max(v_1(t), v_2(t))$ and $g(t) = \min(v_1(t), v_2(t))$ follows. The second line contains an integer $n$, the number of kink points of $h(t)$. The next $n$ lines contain pairs of integers $t_i$ and $h(t_i)$, the kink points of $h(t)$ ($0 = t_1 < t_2 < \dots < t_{n-1} < t_n = T$, $0 \le h(t_i) \le 10^6$). No three consecutive kink points lie on the same straight line. The following lines describe $g(t)$ in the same format. For any $x \in [0; T]$, $g(t) \le h(t)$, and $g(t) = h(t)$ holds at no more than 30 points (in particular, the graphs share no common segments). Each function has between 2 and 100000 kink points.

Output the functions $v_1(t)$ and $v_2(t)$ in the same format as $h(t)$ and $g(t)$. No three consecutive kink points may lie on the same straight line. All numbers in the output must be integers. If there are several solutions, print any of them. At least one solution is guaranteed to exist.