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

Vasya launched his turtle into the lobby, changing its acceleration several times. After plotting a graph of a piecewise linear velocity function v₁(t) he repeated the experiment. Then he has got a piecewise linear continuous function v₂(t) and plotted its graph too.

Before the third try Vasya has realized that it was a bad idea to plot v₁(t) and v₂(t) on the same graph. Because of this, it was not clear which segments belong to which function. Help Vasya to restore graphs, keeping in mind that both experiments lasted the same time T and both times the turtle covered the same distance, which is the length of the lobby.

The first line contains an integer T that is the duration of each of the experiments (2 ≤ T ≤ 10⁶). Then the description of functions h(t) = max(v₁(t), v₂(t)) and g(t) = min(v₁(t), v₂(t)) follows. The second line contains an integer n that is the number of kink points of the function h(t). The next n lines contain pairs of integers t_i and h(t_i) that are kink points of the function h(t) (0 = t₁ < t₂ < … < t_n−1 < t_n = T; 0 ≤ h(t_i) ≤ 10⁶). Any three consecutive kink points don’t lie on the same straight line. In the following lines the function g(t) is described in the same format. For any x ∈ [0; T] g(t) ≤ h(t) and he equality g(t) = h(t) holds for no more than 30 points (in particular, the graphs don’t have common segments). The number of kink points of each function is from 2 to 100 000.

Output functions v₁(t) and v₂(t) in a similar format as h(t) and g(t), including the fact that no three consecutive kink points lie on the same straight line. All numbers in the output should be integers. If this problem has several solutions, output any of them. It’s guaranteed that at least one solution exists.

In the example the length of the lobby is 5.