You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

1S/512M

题目描述

apiadu 正在玩一种策略卡牌游戏。他有一套由 $N$ 张基础卡牌组成的牌组。每张基础卡牌 $i$ 都有两个属性：攻击力 $A_i$ 和防御力 $B_i$。

为了提升牌组的威力，apiadu 可以从 $Q$ 张“增益卡”中选择一张加入牌组。第 $j$ 张增益卡的效果是：为牌组中所有基础卡牌提供 $C_j$ 的攻击力增益和 $D_j$ 的防御力增益。

在游戏中，总得分是所有基础卡牌的战斗力之和。如果选择了第 $j$ 张增益卡，那么第 $i$ 张基础卡牌的战斗力就定义为它生效后的攻击力与防御力的乘积，即 $(A_i + C_j) \times (B_i + D_j)$。

对于每张可选的增益卡，apiadu 想知道，如果选择它，牌组的总得分会是多少？

由于分数可能很大，请将每次计算出的总分对 $998244353$ 取模。

格式

输入格式

第一行包含一个整数 $N$，表示基础卡牌的数量。

接下来 $N$ 行，每行包含两个整数 $A_i$ 和 $B_i$，表示第 $i$ 张基础卡牌的初始攻击力和防御力。

接下来一行包含一个整数 $Q$，表示增益卡的数量。

接下来 $Q$ 行，每行包含两个整数 $C_j$ 和 $D_j$，表示第 $j$ 张增益卡提供的攻击力增益和防御力增益。

输出格式

输出 $Q$ 行，每行一个整数。第 $j$ 行的整数表示如果选择第 $j$ 张增益卡，牌组获得的总得分对 $998244353$ 取模后的结果。

样例

样例输入 #1

2
1 10
2 20
2
3 5
0 1

样例输出 #1

185
53

样例解释 #1

牌组中有两张基础卡牌：(攻击力 $1$, 防御力 $10$) 和 (攻击力 $2$, 防御力 $20$)。

对于第一张增益卡：

• 第一张基础卡牌的战斗力变为: $(1 + 3) \times (10 + 5) = 4 \times 15 = 60$
• 第二张基础卡牌的战斗力变为: $(2 + 3) \times (20 + 5) = 5 \times 25 = 125$
• 总得分：$60 + 125 = 185$

对于第二张增益卡：

• 第一张基础卡牌的战斗力变为: $(1 + 0) \times (10 + 1) = 1 \times 11 = 11$
• 第二张基础卡牌的战斗力变为: $(2 + 0) \times (20 + 1) = 2 \times 21 = 42$
• 总得分：$11 + 42 = 53$

数据规模

对于 $50\%$ 的数据，$1\leq N , Q \leq 1000$。

对于 $100\%$ 的数据，$1 \leq N, Q \leq 10^5$，$0 \leq A_i, B_i, C_i, D_i < 998244353$。