分数: 1100 点
问题陈述
给你一个整数序列 A=(A_1,A_2,\ldots,A_N)。另外,你还得到了正整数 a,b,s,t。可以保证 a 和 b 是 分别为 共质.
您可以对以下四种类型的操作: A:
- 选择一个整数 i 满意 1\leq i\leq N 并添加 a to A_i。此操作成本 s.
- 选择一个整数 i 满意 1\leq i\leq N 并减去 a 来自 A_i。此操作成本 s.
- 选择一个整数 i 满意 1\leq i\leq N 并添加 b to A_i。此操作成本 t.
- 选择一个整数 i 满意 1\leq i\leq N 并减去 b 来自 A_i。此操作成本 t.
答案 Q 查询。在 q-第一个查询,给你一个整数 B_q,所以找到以下值模 998244353:
- 制造所需的最低总成本 A_{1}=A_{2}=\cdots=A_{N}=B_q 按住。可以证明,可以使 A_{1}=A_{2}=\cdots=A_{N}=B_q 按住。
约束
- 1\leq N\leq 2\times 10^5
- 1\leq Q\leq 2\times 10^5
- 1\leq a,b,s,t\leq 5\times 10^8
- a 和 b 互质。
- 1\leq A_i\leq 5\times 10^8
- 1\leq B_q\leq 5\times 10^8
输入
输入由标准输入按以下格式给出:
N Q a b s t A_1 A_2 \ldots A_N B_1 B_2 \ldots B_Q
输出
输出 Q 值以空格分隔。
的 树的 q-th 值应该是最小总成本,模数 998244353,需要制作 A_{1}=A_{2}=\cdots=A_{N}=B_q 按住。
示例输入 1
1 5 3 5 4 3 3 1 2 3 4 5
示例输出 1
7 11 0 11 7
- 通过执行操作 +a, -b on A_1 按顺序,我们可以使 A=(1)。总成本是 4+3=7.
- 通过执行操作 -a, -a, +b on A_1 按顺序,我们可以使 A=(2)。总成本是 4+4+3=11.
- A=(3) 从头开始。总成本是 0.
- 通过执行操作 +a, +a, -b on A_1 按顺序,我们可以使 A=(4)。总成本是 4+4+3=11.
- 通过执行操作 -a, +b on A_1 按顺序,我们可以使 A=(5)。总成本是 4+3=7.
示例输入 2
3 1 3 5 4 3 1 2 3 4
示例输出 2
22
- 通过执行操作 +a on A_1, +b, -a on A_2,和 +a,+a,-b on A_3 按顺序,我们可以使 A=(4,4,4)。总成本是 22.
示例输入 3
5 5 1234 4321 5 5 1 10 100 1000 10000 123 4567 89012345 6 789
示例输出 3
45340 42530 531725 35135 41690