Sur la table sont disposés $n$ tas de blocs, où le nombre initial de blocs dans le $i$-ième tas ($1 \le i \le n$) est $a_i$.

Xiao T et Xiao S fournissent chacun un tamis magique avec une taille de maille $p$ et $q$ respectivement, capables de réduire le nombre de blocs dans les tas couverts en prenant le modulo correspondant, permettant ainsi d'éliminer les blocs en masse. Lorsqu'ils sont déployés naturellement, ces deux tamis couvrent exactement une largeur de $k$ tas de blocs. Ils possèdent une élasticité spéciale qui leur permet de s'étirer librement vers les deux extrémités pour couvrir une plage plus large, mais ils ne peuvent pas être compressés vers l'intérieur. La méthode d'utilisation des tamis magiques est la suivante :

• Sélectionner un intervalle continu de tas de blocs $[l, r]$ d'une longueur d'au moins $k$ et y appliquer le tamis ;
• Choisir l'un des deux tamis magiques, c'est-à-dire choisir $m \in \{p, q\}$ ;
• Pour chaque tas de blocs dans l'intervalle $[l, r]$, remplacer son nombre de blocs par son reste modulo $m$, c'est-à-dire $a_i \leftarrow a_i \pmod m$.

Puisque vous participez à ce jeu, vous ne vous contentez pas de résultats médiocres. Afin d'atteindre le sommet du classement, vous voulez savoir, en utilisant les tamis magiques un nombre arbitraire de fois, quelle est la valeur minimale du nombre total de blocs restants sur la table (c'est-à-dire $\sum_{i=1}^n a_i$).

Entrée

Chaque cas de test contient plusieurs jeux de données. La première ligne de l'entrée contient un entier positif $T$ ($1 \le T \le 10^3$), représentant le nombre de jeux de données. Pour chaque jeu de données :

• La première ligne contient quatre entiers positifs $n, k, p, q$ ($1 \le k \le n \le 10^5$, $1 \le p < q \le 10^9$), représentant respectivement le nombre de tas de blocs, le nombre de tas couverts par le tamis lors de son déploiement naturel, et les tailles de maille des deux tamis magiques.
• La deuxième ligne contient $n$ entiers positifs $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), représentant le nombre initial de blocs dans chaque tas.

Il est garanti que la somme de $n$ sur tous les jeux de données ne dépasse pas $10^5$.

Sortie

Pour chaque jeu de données, affichez sur une ligne un entier non négatif représentant la valeur minimale du nombre total de blocs restants sur la table.

Exemples

Entrée 1

6
1 1 3 4
2 0 26
3 2 10 20
3 1 41 59
4 3 3 4
1 2 3 4
6 4 9 20
18 27 180 9 45 99
7 4 3 5
6 7 14 12 100 78 4
9 4 244 353
9982 4435 3998 2443 5399 8244 3539 9824 4353

Sortie 1

1
11
3
0
4
569

Remarque

Pour le deuxième jeu de données, une méthode permettant d'atteindre le nombre total minimal de 11 blocs restants est la suivante :

• Sélectionner l'intervalle $[1, 4]$ et utiliser le tamis magique de taille 10, le nombre de blocs restants devient $[1, 1, 9]$.

Pour le troisième jeu de données, une méthode permettant d'atteindre le nombre total minimal de 3 blocs restants est la suivante :

• Sélectionner l'intervalle $[2, 4]$ et utiliser le tamis magique de taille 4, le nombre de blocs restants devient $[1, 2, 3, 0]$ ;
• Sélectionner l'intervalle $[1, 3]$ et utiliser le tamis magique de taille 3, le nombre de blocs restants devient $[1, 2, 0, 0]$.