311242: CF1955B. Progressive Square

B. Progressive Squaretime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

A progressive square of size $n$ is an $n \times n$ matrix. Maxim chooses three integers $a_{1,1}$, $c$, and $d$ and constructs a progressive square according to the following rules:

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

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

For example, if $n = 3$, $a_{1,1} = 1$, $c=2$, and $d=3$, then the progressive square looks as follows:

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

Last month Maxim constructed a progressive square and remembered the values of $n$, $c$, and $d$. Recently, he found an array $b$ of $n^2$ integers in random order and wants to make sure that these elements are the elements of that specific square.

It can be shown that for any values of $n$, $a_{1,1}$, $c$, and $d$, there exists exactly one progressive square that satisfies all the rules.

Input

The first line contains an integer $t$ ($1 \le t \le {10} ^ 4$) — the number of test cases.

The first line of each test case contains three integers $n$, $c$, and $d$ ($2 \le n \le 500$, $1 \le c, d \le 10^6$) — the size of the square and the values of $c$ and $d$ as described in the statement.

The second line of each test case contains $n \cdot n$ integers $b_1, b_2, \dots, b_{n \cdot n}$ ($1 \le b_i \le 10^9$) — the elements found by Maxim.

It is guaranteed that the sum of $n ^ 2$ over all test cases does not exceed $25 \cdot {10} ^ 4$.

Output

For each test case, output "YES" in a separate line if a progressive square for the given $n$, $c$, and $d$ can be constructed from the array elements $a$, otherwise output "NO".

You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.

ExampleInput

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

Output

NO
YES
YES
NO
NO

题目大意：
给定一个大小为 n 的渐进方阵，是一个 n×n 的矩阵。Maxim 选择三个整数 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}
\]

上个月 Maxim 构建了一个渐进方阵，并记住了 n，c 和 d 的值。最近，他找到了一个包含 n^2 个整数的数组 b，这些整数顺序随机，并希望确认这些元素是否属于那个特定的方阵。

输入输出数据格式：
输入：
第一行包含一个整数 t（1 ≤ t ≤ 10^4）——测试用例的数量。
每个测试用例的第一行包含三个整数 n，c 和 d（2 ≤ n ≤ 500，1 ≤ c, d ≤ 10^6）——方阵的大小和题目描述中的 c 和 d 的值。
每个测试用例的第二行包含 n×n 个整数 b_1, b_2, …, b_{n×n}（1 ≤ b_i ≤ 10^9）——Maxim 找到的元素。
保证所有测试用例的 n^2 之和不超过 25×10^4。

输出：
对于每个测试用例，如果可以从数组元素 a 构建一个给定 n，c 和 d 的渐进方阵，则输出 "YES"，否则输出 "NO"。
每个字母的输出可以是任何大小写。例如，"yEs"、"yes"、"Yes" 和 "YES" 都将作为肯定答案接受。题目大意： 给定一个大小为 n 的渐进方阵，是一个 n×n 的矩阵。Maxim 选择三个整数 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} \] 上个月 Maxim 构建了一个渐进方阵，并记住了 n，c 和 d 的值。最近，他找到了一个包含 n^2 个整数的数组 b，这些整数顺序随机，并希望确认这些元素是否属于那个特定的方阵。 输入输出数据格式： 输入： 第一行包含一个整数 t（1 ≤ t ≤ 10^4）——测试用例的数量。 每个测试用例的第一行包含三个整数 n，c 和 d（2 ≤ n ≤ 500，1 ≤ c, d ≤ 10^6）——方阵的大小和题目描述中的 c 和 d 的值。 每个测试用例的第二行包含 n×n 个整数 b_1, b_2, …, b_{n×n}（1 ≤ b_i ≤ 10^9）——Maxim 找到的元素。 保证所有测试用例的 n^2 之和不超过 25×10^4。 输出： 对于每个测试用例，如果可以从数组元素 a 构建一个给定 n，c 和 d 的渐进方阵，则输出 "YES"，否则输出 "NO"。 每个字母的输出可以是任何大小写。例如，"yEs"、"yes"、"Yes" 和 "YES" 都将作为肯定答案接受。