P16530 [THUPC 2026 决赛] 积木消除游戏

来自 2026 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2026）决赛。 题解等资源可在 https://github.com/dapingguo8/THUPC2026-final 查看。 > 欣赏完绚丽的幻光留影，大家又被不远处的积木消除小游戏区吸引了目光。 > > 桌面上整齐排列着五颜六色的积木。小 T 和小 S 作为摊主，各自提供了一个能够批量消除积木的魔法筛网。游戏规则很简单：大家可以反复使用这两个筛网进行消除，最终根据桌面上剩余总积木数量进行排名。

桌面上整齐排列着 $n$ 堆积木，第 $i \ (1 \le i \le n)$ 堆的初始数量为 $a_i$。 小 T 和小 S 分别提供了网眼大小为 $p, q$ 的两个魔法筛网，能将覆盖的积木堆按对应的模数取余，从而将积木批量消除。在自然展开时，这两个筛网都恰好跨越 $k$ 堆积木的宽度。它们具有特殊的弹性，可以向两端自由拉伸以覆盖更长的范围，但无法向内压缩收拢。魔法筛网的使用方式如下： - 选定一段长度**至少为 $k$** 的连续的积木区间 $[l, r]$ 并铺上筛网； - 从两个魔法筛网中任选一个，即选定 $m \in \{p, q\}$； - 对于区间 $[l, r]$ 内的每一堆积木，将其数量对 $m$ 取余，即令 $a_i \gets a_i \bmod m$。 既然参与了这场游戏，你自然不满足于平庸的成绩。为了在排行榜上拔得头筹，你想知道，通过反复使用任意次数的魔法筛网，最终桌面上剩余的积木总数（即 $\sum_{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)$，分别表示积木的堆数、筛网自然展开时跨越的积木堆数，以及两个魔法筛网的网眼大小。 - 第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n \ (1 \le a_i \le 10 ^ 9)$，分别表示每堆积木的初始数量。 保证所有测试数据中 $n$ 的和不超过 $10 ^ 5$。

对于每组测试数据，输出一行一个非负整数，表示桌面上剩余总积木数量的最小值。

对于第二组测试数据，一种能使桌面上剩余积木总数达到最小值 $11$ 的操作方式如下： - 选定区间 $[1, 4]$ 并使用网眼大小为 $10$ 的魔法筛网，剩余的积木数量变为 $[1, 1, 9]$。 对于第三组测试数据，一种能使桌面上剩余积木总数达到最小值 $3$ 的操作方式如下： - 选定区间 $[2, 4]$ 并使用网眼大小为 $4$ 的魔法筛网，剩余的积木数量变为 $[1, 2, 3, 0]$； - 选定区间 $[1, 3]$ 并使用网眼大小为 $3$ 的魔法筛网，剩余的积木数量变为 $[1, 2, 0, 0]$。