± ab

AtCoder

IDarc210_f

Time10000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

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$.

Input #2

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$.

Input #3

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

Output #3

45340 42530 531725 35135 41690

API Response (JSON)

{
  "problem": {
    "name": "± ab",
    "description": {
      "content": "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",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 10000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc210_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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**.\nYou can perform the following four types...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments