Le NIT aime les vis rondes. Il aime aussi l'opérateur $\oplus$ parce qu'il lui rappelle les vis rondes, où $\oplus$ représente l'opération OU exclusif bit à bit (Bitwise-XOR).
On définit la valeur $V_a$ d'une suite $a_1, a_2, \cdots, a_n$ par $V_a = a_1 + a_n + \sum_{i=1}^{n-1} (a_i \oplus a_{i+1})$.
Étant donné une suite $a_1, a_2, \cdots, a_n$, vous pouvez effectuer l'opération suivante un nombre arbitraire de fois :
- Choisir un indice $i$ ($1 \le i \le n$), remplacer $a_i$ par n'importe quel entier naturel (positif ou nul) ; cette opération a un coût $C$.
Minimisez la somme de la valeur de la suite et du coût engendré par les opérations. En d'autres termes, soit $p$ le nombre d'opérations effectuées et $V_{a'}$ la valeur de la suite $a$ après les opérations ; vous devez minimiser $pC + V_{a'}$.
Entrée
L'entrée contient plusieurs cas de test. La première ligne de l'entrée contient un entier $T$ ($1 \le T \le 100$), le nombre de cas de test.
Pour chaque cas de test, la première ligne contient deux entiers $n, C$ ($2 \le n \le 10^5, 0 \le C < 2^{19}$), la longueur de la suite et le coût d'une opération.
La deuxième ligne contient $n$ entiers $a_1, a_2, \cdots, a_n$ ($0 \le a_i < 2^{18}$), représentant les éléments de la suite.
Il est garanti que la somme de $n$ sur tous les cas de test ne dépasse pas $2 \times 10^5$.
Sortie
Pour chaque cas de test, affichez un entier sur une seule ligne : la valeur minimale possible de $pC + V_{a'}$.
Exemple
Entrée
3 4 4 1 4 5 6 8 6 6 6 6 1 1 6 6 6 6 7 1 7 2 6 3 5
Sortie
14 24 29
Note
Pour le premier cas de test, une façon d'atteindre le minimum est de transformer la suite en $1, \mathbf{1}, \mathbf{1}, \mathbf{0}$ ; les nombres en gras sont ceux qui ont été modifiés. La valeur finale de la suite est $2$, et $3$ opérations ont été effectuées ; le total valeur + coût vaut $2 + 3 \times 4 = 14$.
Pour le deuxième cas de test, une façon d'atteindre le minimum est de transformer la suite en $6, 6, 6, \mathbf{6}, \mathbf{6}, 6, 6, 6$ ; la valeur finale est $12 + 2 \times 6 = 24$.