Monocarp 将为他的朋友举办一个聚会。他准备了 $$$n$$$ 菜肴并即将上菜。首先,他必须在每道菜中加入一些胡椒粉——否则,菜肴就会变得无味。
第 $$$i$$$ 菜有两个值 $$$a_i$$$ 和 $$$b_i$$$ - 分别是添加红辣椒或添加黑胡椒的美味。 Monocarp 不会在任何菜肴中同时添加两种辣椒,不会多次添加任何辣椒,也不会留下任何不添加辣椒的菜肴。
在添加辣椒之前,Monocarp 应先在一些商店购买上述辣椒。他所在的地区有 $$$m$$$ 商店。其中第 $$$j$$$ 的红辣椒包足以满足 $$$x_j$$$ 份量,而黑胡椒包则足以满足 $$$y_j$$$ 份量。
Monocarp 只去一家商店,购买多个(可能是零)包每种辣椒,这样每道菜都会添加一次辣椒,并且不会留下任何辣椒。更正式地说,如果他购买了$$$x$$$红辣椒包和$$$y$$$黑胡椒包,那么$$$x$$$和$$$y$$$应该是非负的,并且$$$x \cdot x_j + y \cdot y_j$$$应该等于$$$n$$$。
对于每个商店,确定Monocarp仅在该商店购买胡椒包并将胡椒添加到菜肴中后菜肴的最大总味道。如果无法通过上述方式购买套餐,则打印-1。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — 菜肴数量。
接下来的 $$$n$$$ 行的第 $$$i$$$ 行包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i, b_i \le 10^9$$$) - 第 $$$i$$$ 行分别添加红辣椒或添加黑胡椒的味道。
下一行包含一个整数 $$$m$$$ ($$$1 \le m \le 3 \cdot 10^5$$$) — 商店数量。
接下来的 $$$m$$$ 行的第 $$$j$$$ 行包含两个整数 $$$x_j$$$ 和 $$$y_j$$$ ($$$1 \le x_j, y_j \le n$$$) - 分别是第 $$$j$$$ 商店中红胡椒包和黑胡椒包足够的份数。
输出
打印 $$$m$$$ 整数。对于每个商店,打印Monocarp仅在该商店购买胡椒包并将胡椒添加到菜肴中后菜肴的最大总味道。如果不可能购买到每道菜都加一次胡椒粉且没有胡椒粉的包装,请打印-1。
示例
输入 #1
3 5 10 100 50 2 2 4 2 3 1 1 3 2 2 2
输出 #1
62 112 107 -1
输入 #2
10 3 1 2 3 1 1 2 1 6 3 1 4 4 3 1 3 5 3 5 4 10 8 10 9 3 1 4 2 5 8 3 3 5 1 6 7 2 6 7 3 1
输出 #2
26 -1 36 30 -1 26 34 26 -1 36
注意
考虑第一个例子。
在第一家商店,Monocarp只能购买$$$0$$$红辣椒套餐和$$$1$$$黑胡椒套餐。所有菜肴中添加的黑胡椒总计为 $$$10 + 50 + 2 = 62$$$。
在第二家商店中,Monocarp 可以购买任意数量的红胡椒和黑胡椒套餐:$$$0$$$ 和 $$$3$$$、$$$1$$$ 和 $$$2$$$、$$$2$$$ 和 $$$1$$$ 或 $$$3$$$ 和 $$$0$$$。最佳选择是 $$$1$$$ 和 $$$2$$$ 或 $$$2$$$ 和 $$$1$$$。 Monocarp可以在第一道菜中添加黑胡椒,在第二道菜中添加红辣椒,在第三道菜中添加任意胡椒,总计为$$$10 + 100 + 2 = 112$$$。
第三家店Monocarp只能购买$$$1$$$红辣椒套餐和$$$0$$$黑胡椒套餐。添加到所有菜肴中的红辣椒总计为 $$$5 + 100 + 2 = 107$$$。
在第四家商店中,Monocarp 只能购买偶数个包裹。由于 $$$n$$$ 是奇数,因此不可能准确获得 $$$n$$$ 包。因此,答案是$$$-1$$$。