题目描述

有一个纵向 $3$ 格、横向 $N$ 格的网格。自上而下的第 $i$ 行，自左而右的第 $j$ 列的格子记为 $(i, j)$。最初，格子 $(i, j)$ 上写着整数 $i + 3j - 3$。

$N=5$ 时的网格

すぬけ君可以进行若干次如下操作：

• 选择一个 $3 \times 3$ 的正方形区域，将该区域内的整数整体旋转 $180^\circ$。

操作序列示例（蓝色正方形为操作区域）

すぬけ君的目标是使得格子 $(i, j)$ 上写着整数 $a_{i,j}$。请判断すぬけ君是否能够达成目标。

输入格式

输入从标准输入读入，格式如下：

$N$ $a_{1,1}$ $a_{1,2}$ $\ldots$ $a_{1,N}$ $a_{2,1}$ $a_{2,2}$ $\ldots$ $a_{2,N}$ $a_{3,1}$ $a_{3,2}$ $\ldots$ $a_{3,N}$

输出格式

如果すぬけ君能够达成目标，输出 Yes；否则输出 No。

样例 1

输入

5
9 6 15 12 1
8 5 14 11 2
7 4 13 10 3

输出

Yes

样例 2

输入

5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15

输出

No

样例 3

输入

5
1 4 7 10 13
2 5 8 11 14
3 6 9 12 15

输出

Yes

样例 4

输入

6
15 10 3 4 9 16
14 11 2 5 8 17
13 12 1 6 7 18

输出

Yes

样例 5

输入

7
21 12 1 16 13 6 7
20 11 2 17 14 5 8
19 10 3 18 15 4 9

输出

No

说明/提示

限制

• $5 \leq N \leq 10^5$
• $1 \leq a_{i,j} \leq 3N$
• 所有 $a_{i,j}$ 互不相同。

样例解释 1

这是题目描述中的图示例。

样例解释 3

初始状态已经是目标排列。

由 ChatGPT 4.1 翻译