H. Biathlon 2.0
time limit per test
2 seconds
memory limit per test
256 mebibytes
input
standard input
output
standard output

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.

Input

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.

Output

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.

Examples
Input
3
1 4
4 1
3 3
3
1 3
3 1
2 2
Output
7 7 12 
Input
1
1000000000 1000000000
1
1000000000 1000000000
Output
2000000000000000000