2016 年，Biathlon 2.0 世界锦标赛在彼得罗扎沃茨克举行。

Biathlon 2.0 的规则与经典两项有所不同。赛道由 $n$ 个赛段组成。第 $i$ 个赛段包含 $a_i$ 公里的路程和 $b_i$ 个需要击中的目标。为了通过一个赛段，运动员必须跑完所有 $a_i$ 公里的路程并击中所有 $b_i$ 个目标。运动员按从 $1$ 到 $n$ 的顺序通过赛段。每位运动员必须随身携带一把步枪。允许在赛段之间更换步枪。

Berland 国家队拥有 $m$ 种不同的步枪类型。每种步枪类型由两个数字描述：$c_i$ 和 $d_i$，其中 $c_i$ 是使用该类型步枪跑完一公里所需的时间（秒），$d_i$ 是使用该类型步枪击中一个目标所需的时间（秒）。该队拥有任意类型步枪的无限供应。

你的任务是确保 Berland 获胜，并为每个赛段找到一把步枪，以最小化通过该赛段所需的时间。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 5 \cdot 10^5$)，表示赛道中的赛段数量。接下来的 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$ ($0 \le a_i, b_i \le 10^9, a_i + b_i > 0$)，分别表示第 $i$ 个赛段的公里数和目标数。

下一行包含一个整数 $m$ ($1 \le m \le 5 \cdot 10^5$)，表示 Berland 国家队使用的步枪类型数量。

接下来的 $m$ 行，每行包含两个整数 $c_i$ 和 $d_i$ ($1 \le c_i, d_i \le 10^9$)，分别表示第 $i$ 种步枪类型跑完一公里所需的时间和击中一个目标所需的时间。

输出格式

输出 $n$ 个以空格分隔的整数。第 $i$ 个整数表示如果使用最优步枪，通过第 $i$ 个赛段所需的最少时间。

样例

输入 1

3
1 4
4 1
3 3
3
1 3
3 1
2 2

输出 1

7 7 12

输入 2

1
1000000000 1000000000
1
1000000000 1000000000

输出 2

2000000000000000000