{"raw_statement":[{"iden":"problem statement","content":"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:\n\n*   $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:\n\n$\\mathrm{mex}(x, y)$\n\n$y=0$\n\n$y=1$\n\n$y=2$\n\n$x=0$\n\n$1$\n\n$2$\n\n$1$\n\n$x=1$\n\n$2$\n\n$0$\n\n$0$\n\n$x=2$\n\n$1$\n\n$0$\n\n$0$\n\nHow many entries of the matrix are $0, 1,$ and $2$, respectively?"},{"iden":"constraints","content":"*   $1 \\leq N \\leq 500{,}000$\n*   $a_{i,j}$'s given in input are one of $0$, $1$ and $2$."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$a_{1, 1}$ $a_{1, 1}$ $...$ $a_{1, N}$\n$a_{2, 1}$\n$:$\n$a_{N, 1}$"},{"iden":"sample input 1","content":"4\n1 2 0 2\n0\n0\n0"},{"iden":"sample output 1","content":"7 4 5\n\nThe matrix is as follows:\n\n1 2 0 2\n0 1 2 0\n0 2 0 1\n0 1 2 0"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}