Sobre la mesa hay $n$ pilas de bloques dispuestas ordenadamente, donde la cantidad inicial de bloques en la pila $i$ ($1 \le i \le n$) es $a_i$.

Pequeño T y Pequeño S proporcionan dos tamices mágicos con tamaños de malla $p$ y $q$, respectivamente, que pueden eliminar bloques en masa aplicando la operación de módulo a las pilas de bloques cubiertas. Cuando se despliegan naturalmente, ambos tamices cubren exactamente un ancho de $k$ pilas de bloques. Tienen una elasticidad especial que les permite estirarse libremente hacia ambos extremos para cubrir un rango más largo, pero no pueden comprimirse hacia adentro. El uso de los tamices mágicos es el siguiente:

• Seleccionar un intervalo continuo de bloques $[l, r]$ con una longitud de al menos $k$ y colocar el tamiz.
• Elegir uno de los dos tamices mágicos, es decir, seleccionar $m \in \{p, q\}$.
• Para cada pila de bloques en el intervalo $[l, r]$, reemplazar su cantidad por el resto de la división entre $m$, es decir, $a_i \leftarrow a_i \pmod m$.

Como participante en este juego, naturalmente no te conformas con resultados mediocres. Para obtener el primer lugar en la tabla de clasificación, quieres saber cuál es la cantidad mínima total de bloques que pueden quedar sobre la mesa ($\sum_{i=1}^n a_i$) después de usar los tamices mágicos cualquier número de veces.

Cada caso de prueba contiene múltiples conjuntos de datos. La primera línea de la entrada contiene un entero positivo $T$ ($1 \le T \le 10^3$), que indica el número de conjuntos de datos. Para cada conjunto de datos:

• La primera línea contiene cuatro enteros positivos $n, k, p, q$ ($1 \le k \le n \le 10^5$, $1 \le p < q \le 10^9$), que representan el número de pilas de bloques, el número de pilas que cubre el tamiz cuando se despliega naturalmente, y los tamaños de malla de los dos tamices mágicos, respectivamente.
• La segunda línea contiene $n$ enteros positivos $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), que representan la cantidad inicial de bloques en cada pila.

Se garantiza que la suma de $n$ en todos los conjuntos de datos no supera $10^5$.

Para cada conjunto de datos, imprime una línea con un entero no negativo que represente la cantidad mínima total de bloques restantes sobre la mesa.

Ejemplos

Entrada 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

Salida 1

1
11
3
0
4
569

Nota

Para el segundo conjunto de datos, una forma de lograr que la cantidad total de bloques restantes sea el mínimo de 11 es la siguiente:

• Seleccionar el intervalo $[1, 4]$ y usar el tamiz mágico con tamaño de malla 10, la cantidad de bloques restante se convierte en $[1, 1, 9]$.

Para el tercer conjunto de datos, una forma de lograr que la cantidad total de bloques restantes sea el mínimo de 3 es la siguiente:

• Seleccionar el intervalo $[2, 4]$ y usar el tamiz mágico con tamaño de malla 4, la cantidad de bloques restante se convierte en $[1, 2, 3, 0]$;
• Seleccionar el intervalo $[1, 3]$ y usar el tamiz mágico con tamaño de malla 3, la cantidad de bloques restante se convierte en $[1, 2, 0, 0]$.