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 v1(t) he
repeated the experiment. Then he has got a piecewise linear continuous function v2(t)
and plotted its graph too.
Before the third try Vasya has realized that it was a bad idea to
plot v1(t) and v2(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.
Input
The first line contains an integer T that is the duration of each of the experiments (2 ≤ T ≤ 106).
Then the description of functions h(t) = max(v1(t), v2(t)) and
g(t) = min(v1(t), v2(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 ti and h(ti) that are kink points of the function h(t)
(0 = t1 < t2 < … < tn−1 < tn = T; 0 ≤ h(ti) ≤ 106).
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
Output functions v1(t) and v2(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.
Sample
input | output |
---|
6
6
0 2
1 1
2 2
3 1
4 2
6 0
6
0 0
1 1
2 0
3 1
4 0
6 0
| 5
0 2
1 1
2 2
4 0
6 0
5
0 0
1 1
2 0
4 2
6 0
|
Notes
In the example the length of the lobby is 5.
Problem Author: Viktor Kamashev (prepared by Bulat Zaynullin)
Problem Source: Ural Sport Programming Championship 2015