题目描述

我们考虑一个 $N \times N$ 的矩阵。该矩阵第 $i$ 行第 $j$ 列的值记为 $a_{i,j}$。对于满足 $i=1$ 或 $j=1$ 的 $a_{i,j}$，输入会给出其值，取值为 $0$、$1$ 或 $2$。其余的元素按照以下规则确定：

• 对于 $2 \leq i, j \leq N$，有 $a_{i,j} = \mathrm{mex}(a_{i-1,j}, a_{i,j-1})$。其中 $\mathrm{mex}(x, y)$ 按照下表定义：

$\mathrm{mex}(x, y)$	$y=0$	$y=1$	$y=2$
$x=0$	$1$	$2$	$1$
$x=1$	$2$	$0$
$x=2$	$1$

请计算矩阵中值为 $0$、$1$、$2$ 的元素各有多少个。

输入格式

输入通过标准输入给出，格式如下：

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

输出格式

请输出 $0$ 的个数、$1$ 的个数、$2$ 的个数，空格分隔。

样例 1

输入

4
1 2 0 2
0
0
0

输出

7 4 5

说明/提示

限制

• $1 \leq N \leq 500{,}000$
• 输入的 $a_{i,j}$ 均为 $0$、$1$ 或 $2$

样例解释 1

矩阵如下所示：

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

由 ChatGPT 4.1 翻译