ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural Championship 2015

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Physics

Time limit: 1.0 second
Memory limit: 64 MB
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

inputoutput
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
To submit the solution for this problem go to the Problem set: 2051. Physics