CF2215A Interval Mod

给定一个包含 $n$ 个整数的数组 $a$，以及一个参数 $k$ 和一个整数集合 $M=\{p, q\}$。 你可以对 $a$ 执行如下操作任意次（可以执行零次）： - 首先，选择一个区间 $[l,r]$（$1 \le l \le r \le n$）且长度不少于 $k$（即 $r-l+1\ge k$），以及一个整数 $m \in M$； - 然后，对于每个 $l\le i \le r$，执行 $a_i \gets a_i \bmod m$。 你需要求出经过任意次操作后，$\sum\limits_{i=1}^n a_i$ 的最小可能值。

每组数据包含多组测试用例。第一行为测试用例个数 $t$（$1 \le t \le 10^4$）。接下来每个测试用例包含两行。 每个测试用例的第一行包含四个整数 $n$、$k$、$p$ 和 $q$（$1\le k\le n\le 10^5$，$1\le p < q \le 10^9$）——表示数组长度 $a$，区间最小长度参数 $k$ 和集合 $M$ 的两个元素。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1\le a_i\le 10^9$）——数组 $a$ 的元素。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

每组测试用例输出一行，一个整数，表示经过所有操作后，$\sum\limits_{i=1}^n a_i$ 的最小可能值。

在第二个测试用例中，一种能得到 $\sum\limits_{i=1}^n a_i = 11$ 的方法如下： 1. 选择 $[l, r]=[1, 3]$，$m = 10$，此时 $a$ 变为 $[1,1,9]$。 在第三个测试用例中，一种能得到 $\sum\limits_{i=1}^n a_i = 3$ 的方式如下： 1. 选择 $[l, r]=[1, 4]$，$m = 4$，此时 $a$ 变为 $[1,2,3,0]$； 2. 选择 $[l, r]=[2, 4]$，$m = 3$，此时 $a$ 变为 $[1,2,0,0]$。 由 ChatGPT 5 翻译