Contest Duration: - (local time) (100 minutes) Back to Home
E - Mex Mat /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

N \times N の行列を考えます。この行列の i 行目、j 列目の値を a_{i, j} とします。i = 1j = 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

制約

• 1 \leq N \leq 500{,}000
• 入力される a_{i, j} の値はすべて 0, 1, 2 のいずれか

入力

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


出力

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


Score : 800 points

Problem Statement

Consider an N \times N matrix. Let us denote by a_{i, j} the entry in the i-th row and j-th column. For a_{i, j} where i=1 or j=1 holds, its value is one of 0, 1 and 2 and given in the input. The remaining entries are defined as follows:

• a_{i,j} = \mathrm{mex}(a_{i-1,j}, a_{i,j-1}) (2 \leq i, j \leq N) where \mathrm{mex}(x, y) is defined by the following table:
\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

How many entries of the matrix are 0, 1, and 2, respectively?

Constraints

• 1 \leq N \leq 500{,}000
• a_{i,j}'s given in input are one of 0, 1 and 2.

Input

Input is given from Standard Input in the following format:

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


Output

Print the number of 0's, 1's, and 2's separated by whitespaces.

Sample Input 1

4
1 2 0 2
0
0
0


Sample Output 1

7 4 5


The matrix is as follows:

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