Bob 有一个包含 $$$3$$$ 行和 $$$n$$$ 列的网格,每个列包含 $$$a_i$$$ 或 $$$-a_i$$$ 某个整数 $$$1 \leq i \leq n$$$。例如,$$$n=4$$$ 的一种可能的网格如下所示:
$$$$$$\begin{bmatrix} a_1 & -a_2 & -a_3 & -a_2 \\ -a_4 & a_4 & -a_1 & -a_3 \\ a_1 & a_2 & -a_2 & a_4 \end{bmatrix}$$$$$$
Alice 和 Bob 玩游戏如下:
- 鲍勃向爱丽丝展示他的网格。
- Alice 给 Bob 一个她选择的数组 $$$a_1, a_2, \dots, a_n$$$,其元素都是 $$$\mathbf{-1}$$$ 或 $$$\mathbf{1}$$$。
- Bob 将这些值替换到他的网格中,以形成 $$$-1$$$ 和 $$$1$$$ 的网格。
- Bob 按非降序对每列的元素进行排序。
- 如果中间行的所有元素都是 $$$1$$$,则 Alice 获胜;否则,鲍勃获胜。
例如,假设 Alice 向 Bob 提供了上面网格的数组 $$$[1, -1, -1, 1]$$$。然后会发生以下情况(为了清晰起见添加了颜色):
$$$$$$\begin{bmatrix} \color{red}{a_1} & \color{green}{-a_2} & \color{blue}{-a_3} & \color{green}{-a_2} \\ -a_4 & a_4 & \color{red}{-a_1} & \color{blue}{-a_3} \\ \color{red}{a_1} & \color{green}{a_2} & \color{green}{-a_2} & a_4 \end{bmatrix} \xrightarrow{[\color{red}{1},\color{green}{-1},\color{blue}{-1},1]} \begin{bmatrix} \color{red}{1} & \color{green}{1} & \color{blue}{1} & \color{green}{1} \\ -1 & 1 & \color{red}{-1} & \color{blue}{1} \\ \color{red}{1} & \color{green}{-1} & \color{green}{1} & 1 \end{bmatrix} \xrightarrow{\text{对每列进行排序}} \begin{bmatrix} -1 & -1 & -1 & 1 \\ \mathbf{1} & \mathbf{1} & \mathbf{1} & \mathbf{1} \\ 1 & 1 & 1 & 1 \\ \end{bmatrix}\,。 $$$$$$ 由于中间行都是 $$$1$$$,所以爱丽丝获胜。
给定 Bob 的网格,确定 Alice 是否可以选择数组 $$$a$$$ 来赢得比赛。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 500$$$) — Bob 网格的列数。
接下来的三行每行包含 $$$n$$$ 整数,其中第 $$$i$$$ 包含 $$$g_{i,1}, g_{i,2}, \dots, g_{i,n}$$$ ($$$-n \leq g_{i,j} \leq n$$$, $$$g_{i,j} \neq 0$$$),代表鲍勃的网格。
如果输入中存在单元格 $$$x > 0$$$,则 Bob 网格中的该单元格应包含 $$$a_x$$$;如果输入中存在 $$$x < 0$$$,则 Bob 网格中的该单元格应包含 $$$-a_{-x}$$$。请参阅示例输入和注释以更好地理解。
输出
对于每个测试用例,如果 Alice 可以获胜,则输出“YES”(不带引号),否则输出“NO”(不带引号)。
在任何情况下都可以输出“YES”和“NO”(例如,字符串“yEs”、“yes”和“Yes”将被识别为肯定响应)。
示例
输入 #1
4 4 1 -2 -3 -2 -4 4 -1 -3 1 2 -2 4 2 1 2 -1 -2 2 -2 5 1 2 3 4 5 -2 3 -4 -5 -1 3 -5 1 2 2 6 1 3 -6 2 5 2 1 3 -2 -3 -6 -5 -2 -1 -3 2 3 1
输出 #1
YES NO YES NO
注意
声明中描述了第一个测试用例。
在第二个测试用例中,Bob的网格如下:
$$$$$$\begin{bmatrix} a_1 & a_2 \\ -a_1 & -a_2 \\ a_2 & -a_2 \end{bmatrix}$$$$$$
为了使最后一列在排序后中间行有 $$$1$$$,Alice 必须选择 $$$a_2 = -1$$$。然而,不可能选择 $$$a_1$$$ 使得排序时第一列的中间有 $$$1$$$ 。因此,爱丽丝不可能获胜。
在第三个测试用例中,Alice 可以选择 $$$a = [1,1,1,1,1]$$$。