The Biathlon 2.0 World Championship is held in Petrozavodsk in 2016.
Biathlon 2.0 has different rules than the classic one. The racing track consists of n segments. The i-th segment consists of ai kilometers to travel and bi targets to hit. To pass a segment, an athlete must travel all ai kilometers and hit all bi targets. Athletes pass segments in the order from 1 to n. Each athlete must carry a rifle with him. It is allowed to change rifles between segments.
The national team of Berland has m different rifle types at its disposal. Each rifle type is described by two numbers: ci and di, where ci is the number of seconds needed to travel one kilometer with a rifle of this type and di is the number of seconds needed to hit one target with a rifle of this type. The team has an unlimited supply of rifles of any type.
Your task is to ensure Berland victory and find a rifle for each track segment to minimize the number of seconds needed to pass the segment.
The first line contains one integer n (1 ≤ n ≤ 5·105), the number of segments in the track. Each of the next n lines contains two integers ai and bi (0 ≤ ai, bi ≤ 109, ai + bi > 0), the number of kilometers and targets on the i-th track segment.
The next line contains one integer m (1 ≤ m ≤ 5·105), the number of rifle types used by the national team of Berland.
The next m lines contain two integers ci and di (1 ≤ ci, di ≤ 109), the number of seconds needed to travel one kilometer with the i-th rifle type and the number of seconds needed to hit one target with the i-th rifle type.
Print n space-separated integers. The i-th integer must be the number of seconds needed to pass the i-th segment if an optimal rifle is used.
3
1 4
4 1
3 3
3
1 3
3 1
2 2
7 7 12
1
1000000000 1000000000
1
1000000000 1000000000
2000000000000000000
Name |
---|