F - ± ab Editorial /

Time Limit: 10 sec / Memory Limit: 1024 MiB

配点 : 1100 点

問題文

整数列 A=(A_1,A_2,\ldots,A_N) が与えられます．また，正整数 a,b,s,t が与えられます．ただし，a,b は互いに素であることが保証されます．

A に対して，次の 4 種の操作を行うことができます．

  • 1\leq i\leq N を満たす整数 i をひとつ選び，A_i に a を足す．この操作にはコストが s かかる．
  • 1\leq i\leq N を満たす整数 i をひとつ選び，A_i から a を引く．この操作にはコストが s かかる．
  • 1\leq i\leq N を満たす整数 i をひとつ選び，A_i に b を足す．この操作にはコストが t かかる．
  • 1\leq i\leq N を満たす整数 i をひとつ選び，A_i から b を引く．この操作にはコストが 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 番目には，A_{1}=A_{2}=\cdots=A_{N}=B_q が成り立つようにするために必要なコストの総和の最小値を，998244353 で割った余りを出力してください．

入力例 1

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

出力例 1

7 11 0 11 7
  • A_1 に +a, -b する操作を順に行うことで，A=(1) にできます．コストの総和 4+3=7 です．
  • A_1 に -a, -a, +b する操作を順に行うことで，A=(2) にできます．コストの総和 4+4+3=11 です．
  • はじめから A=(3) です．コストの総和は 0 です．
  • A_1 に +a, +a, -b する操作を順に行うことで，A=(4) にできます．コストの総和 4+4+3=11 です．
  • A_1 に -a, +b する操作を順に行うことで，A=(5) にできます．コストの総和 4+3=7 です．

入力例 2

3 1
3 5 4 3
1 2 3
4

出力例 2

22
  • A_1 に +a，A_2 に +b, -a，A_3 に +a,+a,-b という操作を順に行うことで，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

Score : 1100 points

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N). Also, you are given positive integers a,b,s,t. It is guaranteed that a and b are coprime.

You can perform the following four types of operations on A:

  • Choose an integer i satisfying 1\leq i\leq N and add a to A_i. This operation costs s.
  • Choose an integer i satisfying 1\leq i\leq N and subtract a from A_i. This operation costs s.
  • Choose an integer i satisfying 1\leq i\leq N and add b to A_i. This operation costs t.
  • Choose an integer i satisfying 1\leq i\leq N and subtract b from A_i. This operation costs t.

Answer Q queries. In the q-th query, you are given an integer B_q, so find the following value modulo 998244353:

  • The minimum total cost required to make A_{1}=A_{2}=\cdots=A_{N}=B_q hold. It can be proved that it is possible to make A_{1}=A_{2}=\cdots=A_{N}=B_q hold.

Constraints

  • 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 and b are coprime.
  • 1\leq A_i\leq 5\times 10^8
  • 1\leq B_q\leq 5\times 10^8

Input

The input is given from Standard Input in the following format:

N Q
a b s t
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_Q

Output

Output Q values separated by spaces.

The q-th value should be the minimum total cost, modulo 998244353, required to make A_{1}=A_{2}=\cdots=A_{N}=B_q hold.

Sample Input 1

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

Sample Output 1

7 11 0 11 7
  • By performing operations +a, -b on A_1 in order, we can make A=(1). The total cost is 4+3=7.
  • By performing operations -a, -a, +b on A_1 in order, we can make A=(2). The total cost is 4+4+3=11.
  • A=(3) from the beginning. The total cost is 0.
  • By performing operations +a, +a, -b on A_1 in order, we can make A=(4). The total cost is 4+4+3=11.
  • By performing operations -a, +b on A_1 in order, we can make A=(5). The total cost is 4+3=7.

Sample Input 2

3 1
3 5 4 3
1 2 3
4

Sample Output 2

22
  • By performing operations +a on A_1, +b, -a on A_2, and +a,+a,-b on A_3 in order, we can make A=(4,4,4). The total cost is 22.

Sample Input 3

5 5
1234 4321 5 5
1 10 100 1000 10000
123 4567 89012345 6 789

Sample Output 3

45340 42530 531725 35135 41690