День народження Сакурако#11712

День народження Сакурако

1 секунда

256 мегабайтів

Легка

Сьогодні день народження Сакурако, тому ви вирішили зробити гарний подарунок. Ви вважаєте, що найкращий подарунок — це масив із $n$ однакових цілих чисел. На жаль, ви не змогли знайти такий масив. Однак, ви розумні й можете змінювати будь-який елемент масиву рівно на $k$ за одну операцію. Іншими словами, якщо у вас є масив $a$ , ви можете вибрати ціле число $i$ ( $1 \leq i \leq n$ 1 \leq i \leq n) і замінити $a_{i}$ a_i на $a_{i} - k$ a_i - k або $a_{i} + k$ a_i + k. Ви хочете зробити Сакурако щасливою, тому потрібно визначити, чи можна зробити всі елементи масиву однаковими.

Наприклад, якщо у вас є масив $[10, 16, 12, 10, 20]$ [10, 16, 12, 10, 20] і $k = 2$ k = 2, ви можете зробити всі елементи рівними $12$ . Для цього додайте $k$ до першого та четвертого елементів ( $a_{1} + k = 10 + 2 = 12$ a_1 + k = 10 + 2 = 12), відніміть $k$ від другого елемента двічі ( $a_{2} - 2 \cdot k = 16 - 4 = 12$ a_2 - 2 \cdot k = 16 - 4 = 12), не змінюйте третій елемент, та відніміть $k$ від п'ятого елемента чотири рази ( $a_{5} - 4 \cdot k = 20 - 8 = 12$ a_5 - 4 \cdot k = 20 - 8 = 12).

Вхідні дані

Перший рядок містить одне ціле число $t$ ( $1 \leq t \leq 1 0^{5}$ 1 \leq t \leq 10^5) — кількість масивів.

Кожен масив описується двома рядками.

Перший рядок містить два цілих числа $n$ і $k$ ( $1 \leq n \leq 2 \cdot 1 0^{5}$ 1 \leq n \leq 2 \cdot 10^5, $1 \leq k \leq 1 0^{9}$ 1 \leq k \leq 10^9).

Другий рядок містить $n$ цілих чисел $a_{1}, \dots, a_{n}$ a_1, \ldots, a_n ( $1 \leq a_{i} \leq 1 0^{9}$ 1 \leq a_i \leq 10^9).

Гарантується, що сума $n$ по всіх тестах не перевищує $2 \cdot 1 0^{5}$ 2 \cdot 10^5.

Вихідні дані

Для кожного масиву виведіть "YES", якщо можна зробити всі елементи однаковими, або "NO" інакше.

Приклади

Приклад

Примітка

Перший приклад пояснено вище.

У другому прикладі відповідь — "YES", адже можна зробити всі числа рівними $123$ .

У третьому прикладі відповідь — "NO", адже можна довести, що п'ятий елемент не вдасться зробити рівним жодному іншому елементу масиву після будь-якої кількості операцій.

Оцінювання

(3 бали): $k = 2$ k = 2;
(8 балів): $a_{i} \leq 100$ a_i \leq 100 для всіх масивів;
(18 балів): $n \leq 1000$ n \leq 1000 для всіх масивів; гарантовано, що сума $n$ по всіх тестах не перевищує $2000$ .
(21 бал): без додаткових обмежень.