2 - Dreams of Divisibility

Every night, Mario dreams of divisibility problems. In one such dream, Mario is given an array $a$ of length $n$, and a number $k$. He performs as many operations as he wants to this array; in the end, he wants to make every element divisible by $k$. In a single operation, Mario selects two indices $i$ and $j$ (in particular, he can choose $i = j$), and does $a[i] = a[i] + a[j]$. Help Mario