← 返回题目列表

AtCoder · arc210_f

F. 正负 ab

中文机器翻译题面 查看原题

分数: 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