Problem Statement

Consider an $N\times N$ matrix. Let us denote by ai,j​ the entry in the $i$-th row and $j$-th column. For ai,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:

• ai,j​=mex(ai−1,j​,ai,j−1​)(2≤i,j≤N) where $\mathrm{m}\mathrm{e}\mathrm{x}(x,y)$ is defined by the following table:

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

Constraints

• $1\le N\le 500,000$
• ai,j​'s given in input are one of $0$, $1$ and $2$.

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