题目描述

考虑一个 $N \times N$ 的矩阵。我们用 $a_{i, j}$ 表示第 $i$ 行第 $j$ 列的元素。对于满足 $i=1$ 或 $j=1$ 的 $a_{i, j}$，其取值为 $0$, $1$ 和 $2$ 中的一个，并且已经在输入中给出。剩下的元素按照以下方式定义：

• $a_{i,j} = \mathrm{mex}(a_{i-1,j}, a_{i,j-1}) (2 \leq i, j \leq N)$，其中 $\mathrm{mex}(x, y)$ 由以下表格定义：

$\mathrm{mex}(x, y)$

$y=0$

$y=1$

$y=2$

$x=0$

$1$

$2$

$1$

$x=1$

$2$

$0$

$0$

$x=2$

$1$

$0$

$0$

矩阵中的元素分别有多少个是 $0$、$1$ 和 $2$？

约束条件

• $1 \leq N \leq 500{,}000$
• 输入中给定的 $a_{i,j}$ 的取值为 $0$, $1$ 和 $2$ 之一。

输入

从标准输入读入输入数据的格式如下：

$N$

$a_{1, 1}$ $a_{1, 2}$ $...$ $a_{1, N}$

$a_{2, 1}$ $a_{2, 2}$ $...$ $a_{2, N}$

$:$

$a_{N, 1}$ $a_{N, 2}$ $...$ $a_{N, N}$

输出

以空格分隔输出矩阵中 $0$、$1$ 和 $2$ 的个数。

示例输入 1

4
1 2 0 2
0
0
0

示例输出 1

7 4 5

矩阵如下所示：

1 2 0 2
0 1 2 0
0 2 0 1
0 1 2 0