B. Прогрессивный квадрат
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Прогрессивный квадрат размера $$$n$$$ — это матрица размера $$$n \times n$$$. Максим выбирает три натуральных числа $$$a_{1,1}$$$, $$$c$$$ и $$$d$$$ и строит прогрессивный квадрат по следующим правилам:

$$$$$$a_{i+1,j} = a_{i,j} + c$$$$$$

$$$$$$a_{i,j+1} = a_{i,j} + d$$$$$$

Например, если $$$n = 3$$$, $$$a_{1,1} = 1$$$, $$$c=2$$$ и $$$d=3$$$, то прогрессивный квадрат выглядит следующим образом:

$$$$$$ \begin{pmatrix} 1 & 4 & 7 \\ 3 & 6 & 9 \\ 5 & 8 & 11 \end{pmatrix} $$$$$$

В прошлом месяце Максим построил прогрессивный квадрат и запомнил значения $$$n$$$, $$$c$$$ и $$$d$$$. Недавно он нашёл массив $$$b$$$ из $$$n^2$$$ целых чисел, идущих в случайном порядке и хочет убедиться, что эти элементы являются элементами того самого квадрата.

Можно показать, что при любых значениях $$$n$$$, $$$a_{1,1}$$$, $$$c$$$ и $$$d$$$ существует ровно один прогрессивный квадрат, удовлетворяющий всем правилам.

Входные данные

В первой строке задано целое число $$$t$$$ ($$$1 \le t \le {10} ^ 4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит три целых числа $$$n$$$, $$$c$$$ и $$$d$$$ ($$$2 \le n \le 500$$$, $$$1 \le c, d \le 10^6$$$) — размер квадрата и значения $$$c$$$ и $$$d$$$, описанные в условии.

Вторая строка каждого набора содержит $$$n \cdot n$$$ целых чисел $$$b_1, b_2, \dots, b_{n \cdot n}$$$ ($$$1 \le b_i \le 10^9$$$) — элементы, которые нашёл Максим.

Гарантируется, что сумма $$$n ^ 2$$$ по всем наборам входных данных не превосходит $$$25 \cdot {10} ^ 4$$$.

Выходные данные

Для каждого набора входных данных в отдельной строке выведите «YES», если прогрессивный квадрат для данных $$$n$$$, $$$c$$$ и $$$d$$$ может быть составлен из элементов массива $$$a$$$, в противном случае выведите «NO».

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
5
3 2 3
3 9 6 5 7 1 10 4 8
3 2 3
3 9 6 5 7 1 11 4 8
2 100 100
400 300 400 500
3 2 3
3 9 6 6 5 1 11 4 8
4 4 4
15 27 7 19 23 23 11 15 7 3 19 23 11 15 11 15
Выходные данные
NO
YES
YES
NO
NO