#P1955B. Progressive Square

    ID: 8754 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 3 上传者: 标签>constructive algorithmsdata structuresimplementationsortings*1000

Progressive Square

Description

A progressive square of size nn is an n×nn \times n matrix. Maxim chooses three integers a1,1a_{1,1}, cc, and dd and constructs a progressive square according to the following rules:

ai+1,j=ai,j+ca_{i+1,j} = a_{i,j} + c

ai,j+1=ai,j+da_{i,j+1} = a_{i,j} + d

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

(1473695811) \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 nn, cc, and dd. Recently, he found an array bb of n2n^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 nn, a1,1a_{1,1}, cc, and dd, there exists exactly one progressive square that satisfies all the rules.

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

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

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

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

For each test case, output "YES" in a separate line if a progressive square for the given nn, cc, and dd can be constructed from the array elements aa, 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.

Input

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

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

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

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

Output

For each test case, output "YES" in a separate line if a progressive square for the given nn, cc, and dd can be constructed from the array elements aa, 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.

样例输入 1

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

样例输出 1

NO
YES
YES
NO
NO