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=0y=1y=2x=0121x=1200x=2100
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-----
4
1 2 0 2
0
0
0

-----Sample Output-----
7 4 5

The matrix is as follows:
1 2 0 2
0 1 2 0
0 2 0 1
0 1 2 0


Difficulty: competition

Starter code:

Solutions:
def met(x,y):
  if x*y>0:return 0
  if (x+y)%2==0:return 1
  return 2
def main0(n,a0,a1):
  ret=[0]*3
  mat=[[0]*n for _ in range(n)]
  for i in range(1,n):
    mat[0][i]=a0[i]
    mat[i][0]=a1[i-1]
    ret[a1[i-1]]+=1
    ret[a0[i]]+=1
  mat[0][0]=a0[0]
  ret[a0[0]]+=1
  for j in range(1,n):
    for i in range(1,n):
      mat[i][j]=met(mat[i][j-1],mat[i-1][j])
      ret[mat[i][j]]+=1
  #for x in mat:print(*x)
  return ret

def main1(n,a0,a1):
  ret=[0]*3

  a1=[a0[0]]+a1
  for i in range(1,n):
    ret[a1[i]]+=1
    ret[a0[i]]+=1
  ret[a0[0]]+=1

  b0,b1=[a1[1]],[a0[1]]
  for i in range(1,n):
    b0.append(met(b0[-1],a0[i]))
    b1.append(met(b1[-1],a1[i]))
    ret[b0[-1]]+=1
    ret[b1[-1]]+=1
  ret[b0[1]]-=1

  c0=[a1[2],b1[2]]
  c1=[a0[2],b0[2]]
  for i in range(2,n):
    c0.append(met(c0[-1],b0[i]))
    c1.append(met(c1[-1],b1[i]))
    ret[c0[-1]]+=1
    ret[c1[-1]]+=1
  ret[c0[2]]-=1

  d0=[a1[3],b1[3],c1[3]]
  d1=[a0[3],b0[3],c0[3]]
  for i in range(3,n):
    d0.append(met(d0[-1],c0[i]))
    d1.append(met(d1[-1],c1[i]))
    ret[d0[-1]]+=1
    ret[d1[-1]]+=1
  ret[d0[3]]-=1

  for i in range(4,n):
    ret[d0[i]]+=n-i-1
    ret[d1[i]]+=n-i-1
  ret[d0[3]]+=n-4
  """
  print(*a0)
  print(*b0)
  print(*c0)
  print(*d0)
  for i in range(4,n):
    print(a1[i],b1[i],c1[i],d1[i])
  """
  return ret


n=int(input())
a0=list(map(int,input().split()))
a1=[int(input()) for _ in range(n-1)]
if n<10:
  ret=main0(n,a0,a1)
else:
  ret=main1(n,a0,a1)
print((*ret))


## coding: UTF-8

def mex(x,y):
    if(x*y>0):
        return 0
    elif(x == 1 and y == 0):
        return 2
    elif(x == 0 and y == 1):
        return 2
    else:
        return 1

'''
import random

N = 15
matrix = []
for i in range(N):
    matrix.append([7] * N)

for i in range(N):
    matrix[0][i] = random.randint(0,2)
for j in range(1, N):
    matrix[j][0] = random.randint(0,2)

for i in range(N):
    print(matrix[i])





for i in range(1, N):
    for j in range(1, N):
        matrix[i][j] = mex(matrix[i-1][j], matrix[i][j-1])

print('~~~~~~~~~~~~~~~~~~~~~~~~~~~')
for i in range(N):
    print(matrix[i])
gutyoku = [0,0,0]
for i in range(N):
    for j in range(N):
        gutyoku[matrix[i][j]] += 1
print(gutyoku)



print('~~~~~~~~~~~~~~~~~~~~~~~+++++++++~~~~~~~~~~~')
'''







counter = [0,0,0]



N = int(input())
#N = 15

if(N == 1):
    counter[int(input())] += 1
    print(('{} {} {}'.format(counter[0], counter[1], counter[2])))




elif(N == 2):
    A = list(map(int,input().split()))
    B = int(input())
    counter[A[0]] += 1
    counter[A[1]] += 1
    counter[B] += 1
    counter[mex(A[1], B)] += 1
    print(('{} {} {}'.format(counter[0], counter[1], counter[2])))

else:
    A = list(map(int,input().split()))
    #A = matrix[0]
    B = []
    for i in range(N-1):
        B.append(int(input()))
        #B.append(matrix[i+1][0])

    matrix = []
    #for i in range(N):
        #matrix.append([7] * N)

    #matrix[0] = A
    matrix.append(A)
    for j in range(1, N):
        #matrix[j][0] = B[j-1]
        matrix.append([B[j-1]])

    
    #for i in range(N):
        #print(matrix[i])
    
    #print(-1)

    
    for i in range(1, 3):
        for j in range(1, N):
            #matrix[i][j] = mex(matrix[i-1][j], matrix[i][j-1])
            matrix[i].append(mex(matrix[i-1][j], matrix[i][j-1]))

    for i in range(3, N):
        for j in range(1,3):
            #matrix[i][j] = mex(matrix[i-1][j], matrix[i][j-1])   
            matrix[i].append(mex(matrix[i-1][j], matrix[i][j-1]))     

    #for i in range(N):
        #print(matrix[i])

    
    counter = [0, 0, 0]
    for i in range(3):
        for j in range(N):
            counter[matrix[i][j]] += 1

    for i in range(3, N):
        for j in range(3):
            counter[matrix[i][j]] += 1

    #print(counter)

    #print('check')
    #for i in range(N):
        #print(matrix[i])
    
    for i in range(3, 4):
        for j in range(3, N):
            #matrix[i][j] = mex(matrix[i-1][j], matrix[i][j-1])
            #counter[matrix[i][j]] += N-j
            matrix[i].append(mex(matrix[i-1][j], matrix[i][j-1]))
            counter[mex(matrix[i-1][j], matrix[i][j-1])] += N-j
            #print(matrix[i][j], N-j)

    for i in range(4, N):
        for j in range(3, 4):
            #matrix[i][j] = mex(matrix[i-1][j], matrix[i][j-1])      
            #counter[matrix[i][j]] += N-i
            matrix[i].append(mex(matrix[i-1][j], matrix[i][j-1]))
            counter[mex(matrix[i-1][j], matrix[i][j-1])] += N-i
            #print(matrix[i][j], N-i)

    #for i in range(N):
        #print(matrix[i])


    #print(counter)

    print(('{} {} {}'.format(counter[0], counter[1], counter[2])))


mex = [
    [1, 2, 1],
    [2, 0, 0],
    [1, 0, 0]
]

N, *I = map(int, open(0).read().split())

A = [I[:N]]
for i, a in enumerate(I[N:], 1):
    M = N if i < 4 else min(4, N)

    Ai = [a]
    for j in range(1, M):
        Ai.append(mex[A[-1][j]][Ai[-1]])

    A.append(Ai)

ans = [0, 0, 0]
for i, Ai in enumerate(A):
    for j, aij in enumerate(Ai):
        ans[aij] += N - max(i, j) if i >= 3 and j >= 3 else 1

print(*ans)

import sys
input = sys.stdin.readline
def solve():
    N = int(input())
    A = list(map(int,input().split()))
    B = [int(input()) for i in range(N-1)]

    def mex(x,y):
        if x+y==1: return 2
        if x==0 or y==0: return 1
        return 0

    n = min(4,N)
    arr = [[-1]*n for _ in range(n)]
    for i,a in enumerate(A):
        if i>=4: break
        arr[0][i] = a
    for i,b in enumerate(B):
        if i+1>=4: break
        arr[i+1][0] = b
    for i in range(1,n):
        for j in range(1,n):
            arr[i][j] = mex(arr[i-1][j], arr[i][j-1])

    ctr = [0,0,0]
    for i in range(n):
        for j in range(n):
            ctr[arr[i][j]] += 1
    if N <= 4:
        print(*ctr)
        return

    arrtop = [[-1]*(N-3) for _ in range(4)]
    for i in range(4):
        arrtop[i][0] = arr[i][-1]
    for j in range(4,N):
        arrtop[0][j-3] = A[j]
    for i in range(1,4):
        for j in range(1,N-3):
            arrtop[i][j] = mex(arrtop[i-1][j], arrtop[i][j-1])
            ctr[arrtop[i][j]] += (1 if i<3 else N-3-j)
    for a in A[4:]:
        ctr[a] += 1

    arrleft = [[-1]*4 for _ in range(N-3)]
    for j in range(4):
        arrleft[0][j] = arr[-1][j]
    for i in range(4,N):
        arrleft[i-3][0] = B[i-1]
    for i in range(1,N-3):
        for j in range(1,4):
            arrleft[i][j] = mex(arrleft[i-1][j], arrleft[i][j-1])
            ctr[arrleft[i][j]] += (1 if j<3 else N-3-i)
    for b in B[3:]:
        ctr[b] += 1

    ctr[arr[-1][-1]] += N-4
    print(*ctr)

solve()

def M(x,y):return[[1,2,1],[2,0,0],[1,0,0]][x][y]
n=int(input())
a=[list(map(int,input().split()))]
for i in range(n-1):
 a.append([int(input())])
 if i<3:
  for j in range(n-1):a[i+1].append(M(a[i][j+1],a[i+1][j]))
 else:
  for j in range(min(4,n)-1):a[i+1].append(M(a[i][j+1],a[i+1][j]))
A=[0,0,0]
for i in range(n):
 for j in range(len(a[i])):
  if i>=3and j>=3:A[a[i][j]]+=n-max(i,j)
  else:A[a[i][j]]+=1
print(*A)

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
B = [int(input()) for i in range(N-1)]

def mex(x,y):
    if x+y==1: return 2
    if x==0 or y==0: return 1
    return 0

n = min(4,N)
arr = [[-1]*n for _ in range(n)]
for i,a in enumerate(A):
    if i>=4: break
    arr[0][i] = a
for i,b in enumerate(B):
    if i+1>=4: break
    arr[i+1][0] = b
for i in range(1,n):
    for j in range(1,n):
        arr[i][j] = mex(arr[i-1][j], arr[i][j-1])

from collections import Counter
ctr = Counter()
for i in range(n):
    for j in range(n):
        ctr[arr[i][j]] += 1
if N <= 4:
    print(ctr[0], ctr[1], ctr[2])
    return

arrtop = [[-1]*(N-3) for _ in range(4)]
for i in range(4):
    arrtop[i][0] = arr[i][-1]
for j in range(4,N):
    arrtop[0][j-3] = A[j]
for i in range(1,4):
    for j in range(1,N-3):
        arrtop[i][j] = mex(arrtop[i-1][j], arrtop[i][j-1])
for i in range(4):
    for j in range(1,N-3):
        ctr[arrtop[i][j]] += (1 if i<3 else N-3-j)

arrleft = [[-1]*4 for _ in range(N-3)]
for j in range(4):
    arrleft[0][j] = arr[-1][j]
for i in range(4,N):
    arrleft[i-3][0] = B[i-1]
for i in range(1,N-3):
    for j in range(1,4):
        arrleft[i][j] = mex(arrleft[i-1][j], arrleft[i][j-1])
for i in range(1,N-3):
    for j in range(4):
        ctr[arrleft[i][j]] += (1 if j<3 else N-3-i)

ctr[arr[-1][-1]] += N-4
print(ctr[0], ctr[1], ctr[2])

import sys

input = sys.stdin.readline

mex = [[1, 2, 1], [2, 0, 0], [1, 0, 0]]

N = int(input())
a = [list(map(int, input().split()))]
for i in range(1, N):
    a.append([int(input())])
    # 最初の4行 / 4列のみを愚直に計算する
    if i < 4:
        stop = N
    else:
        stop = min(4, N)
    for j in range(1, stop):
        a[i].append(mex[a[i - 1][j]][a[i][j - 1]])

count = [0, 0, 0]
for i, ai in enumerate(a):
    for j, aij in enumerate(ai):
        if i >= 3 and j >= 3:
            count[aij] += N - max(i, j)
        else:
            count[aij] += 1
print(*count)

n = int(input())
a = list(map(int, input().split()))
d = [0] * 3
def update(u):
    for i in u:
        d[i] += 1
MEX = {(0, 0): 1, (0, 1): 2, (0, 2): 1, (1, 1): 0, (1, 2): 0, (2, 2): 0}
def mex(u, v):
    return MEX[(min(u, v), max(u, v))]
def proc(v):
    u = [int(input())]
    for i in range(1, len(v)):
        u.append(mex(u[-1], v[i]))
    return u
update(a)
for _ in range(2, min(5, n + 1)):
    a = proc(a)
    update(a)
for j in range(4, n):
    d[a[j - 1]] += n - j
a = a[:4]
for i in range(5, n + 1):
    a = proc(a)
    update(a)
    d[a[3]] += n - i
print(*d)

import sys
input = lambda: sys.stdin.readline().rstrip()
def mex(i, j):
    if i == 0:
        return 2 if j == 1 else 1
    if i == 1:
        return 0 if j else 2
    return 0 if j else 1

ans = [0, 0, 0]
N = int(input())

if N < 10:
    X = [[0] * N for _ in range(N)]
    A = [int(a) for a in input().split()]
    for i, a in enumerate(A):
        X[0][i] = a
        ans[a] += 1
    for i in range(1, N):
        a = int(input())
        X[i][0] = a
        ans[a] += 1
    for i in range(1, N):
        for j in range(1, N):
            a = mex(X[i][j-1], X[i-1][j])
            X[i][j] = a
            ans[a] += 1
    print((*ans))
    return

K = 3
X = [[0] * (N if i <= K else K + 1) for i in range(N)]
A = [int(a) for a in input().split()]
for i, a in enumerate(A):
    X[0][i] = a
    ans[a] += 1
for i in range(1, N):
    a = int(input())
    X[i][0] = a
    ans[a] += 1

for i in range(1, N):
    Xi = X[i]
    Xi1 = X[i-1]
    for j in range(1, K):
        a = mex(Xi[j-1], Xi1[j])
        ans[a] += 1
        X[i][j] = a
for i in range(1, K):
    Xi = X[i]
    Xi1 = X[i-1]
    for j in range(K, N):
        a = mex(Xi[j-1], Xi1[j])
        ans[a] += 1
        X[i][j] = a

for i in range(K, N):
    j = K
    a = mex(X[i][j-1], X[i-1][j])
    X[i][j] = a
    ans[a] += N - i
for j in range(K + 1, N):
    i = K
    a = mex(X[i][j-1], X[i-1][j])
    X[i][j] = a
    ans[a] += N - j

print((*ans))


I=lambda:list(map(int,input().split()))
def med(a,b):
    if a==0 and b==0 or a==0 and b==2 or a==2 and b==0:
        return 1
    elif a==0 and b==1 or a==1 and b==0:
        return 2
    else:return 0
nagasa=4
N,=I()
A0=I()
AA=[A0]
Av=[A0[0]]+[int(input()) for _ in range(N-1)]
if N<=nagasa:
    for l in range(1,N):
        Ai=[Av[l]]
        for i in range(1,N):
            Ai.append(med(AA[l-1][i], Ai[-1]))
        AA+=[Ai]
    print(*(sum(al.count(i) for al in AA) for i in range(3)))
    return

for l in range(1,nagasa):
    Ai=[Av[l]]
    for i in range(1,N):
        Ai.append(med(AA[l-1][i], Ai[-1]))
    AA+=[Ai]
BB=[Av]
for c in range(1,nagasa):
    Bi=[A0[c]]
    for i in range(1,N):
        Bi.append(med(BB[c-1][i], Bi[-1]))
    BB+=[Bi]
*box,=(sum(al[:nagasa].count(i) for al in AA) for i in range(3))
*ass,=(sum(al.count(i) for al in AA) for i in range(3))
*bss,=(sum(bl.count(i) for bl in BB) for i in range(3))
less=[ass[i]+bss[i]-box[i] for i in range(3)]
less[AA[nagasa-1][nagasa-1]]+=N-nagasa
for i,a in enumerate(AA[nagasa-1]):
    if i<nagasa:continue
    less[a]+=N-1-i
for i,b in enumerate(BB[nagasa-1]):
    if i<nagasa:continue
    less[b]+=N-1-i
print(*less)

N = int(input())
# from random import randint
if N<=5:
  A = [[0]*N for _ in range(N)]
  A[0] = list(map(int, input().split()))
  for i in range(1,N):
    A[i][0] = int(input())
  for i in range(1,N):
    for j in range(1,N):
      lis = [0]*3
      lis[A[i-1][j]] = 1
      lis[A[i][j-1]] = 1
      for k in range(3):
        if lis[k]==0:
          A[i][j] = k
          break
  lis = [0]*3
  for i in range(N):
    for j in range(N):
      lis[A[i][j]] += 1
else:
  A = [[0]*N for _ in range(4)]
  A[0] = list(map(int, input().split()))
  B = [[0]*4 for _ in range(N)]
  for i in range(1,N):
    B[i][0] = int(input())
  for i in range(1,4):
    A[i][0] = B[i][0]
  for j in range(4):
    B[0][j] = A[0][j]

  # A[0] = [randint(0,2) for _ in range(N)]
  # for i in range(N-1):
    # A[i+1][0] = randint(0,2)
  for i in range(1,4):
    for j in range(1,N):
      lis = [0]*3
      lis[A[i-1][j]] = 1
      lis[A[i][j-1]] = 1
      for k in range(3):
        if lis[k]==0:
          A[i][j] = k
          break
  for i in range(1,N):
    for j in range(1,4):
      lis = [0]*3
      lis[B[i-1][j]] = 1
      lis[B[i][j-1]] = 1
      for k in range(3):
        if lis[k]==0:
          B[i][j] = k
          break
  lis = [0]*3
  for i in range(3):
    for j in range(N):
      lis[A[i][j]] += 1
  for i in range(3,N):
    for j in range(3):
      lis[B[i][j]] += 1
  for j in range(3,N):
    lis[A[3][j]] += N-j
  for i in range(4,N):
    lis[B[i][3]] += N-i
print((*lis))



import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))
B=[A[0]]+[int(input()) for i in range(N-1)]

if N<=10:
    LIST=[[-1]*N for i in range(N)]
    LIST[0]=A
    for i in range(N):
        LIST[i][0]=B[i]

    for i in range(1,N):
        for j in range(1,N):
            SET={LIST[i-1][j],LIST[i][j-1]}

            if not (0 in SET):
                LIST[i][j]=0
            elif not (1 in SET):
                LIST[i][j]=1
            else:
                LIST[i][j]=2

    ZERO=0
    ONE=0
    TWO=0

    for i in range(N):
        ZERO+=LIST[i].count(0)
        ONE+=LIST[i].count(1)
        TWO+=LIST[i].count(2)

    print(ZERO,ONE,TWO)

    return

    


LIST1=[[-1]*N for i in range(4)]
LIST1[0]=A
LIST1[1][0]=B[1]
LIST1[2][0]=B[2]
LIST1[3][0]=B[3]

for i in range(1,4):
    for j in range(1,N):
        SET={LIST1[i-1][j],LIST1[i][j-1]}

        if not (0 in SET):
            LIST1[i][j]=0
        elif not (1 in SET):
            LIST1[i][j]=1
        else:
            LIST1[i][j]=2

LIST2=[[-1]*N for i in range(4)]
LIST2[0]=B
LIST2[1][0]=A[1]
LIST2[2][0]=A[2]
LIST2[3][0]=A[3]

for i in range(1,4):
    for j in range(1,N):
        SET={LIST2[i-1][j],LIST2[i][j-1]}

        if not (0 in SET):
            LIST2[i][j]=0
        elif not (1 in SET):
            LIST2[i][j]=1
        else:
            LIST2[i][j]=2

ZERO=0
ONE=0
TWO=0
k=1

for i in range(N-1,2,-1):
    if LIST1[3][i]==0:
        ZERO+=k
    elif LIST1[3][i]==1:
        ONE+=k
    else:
        TWO+=k
    k+=1

k=1
for i in range(N-1,3,-1):
    if LIST2[3][i]==0:
        ZERO+=k
    elif LIST2[3][i]==1:
        ONE+=k
    else:
        TWO+=k
    k+=1

ZERO+=LIST1[0].count(0)+LIST1[1].count(0)+LIST1[2].count(0)+LIST2[0][3:].count(0)+LIST2[1][3:].count(0)+LIST2[2][3:].count(0)
ONE+=LIST1[0].count(1)+LIST1[1].count(1)+LIST1[2].count(1)+LIST2[0][3:].count(1)+LIST2[1][3:].count(1)+LIST2[2][3:].count(1)
TWO+=LIST1[0].count(2)+LIST1[1].count(2)+LIST1[2].count(2)+LIST2[0][3:].count(2)+LIST2[1][3:].count(2)+LIST2[2][3:].count(2)

print(ZERO,ONE,TWO)

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

sys.setrecursionlimit(10**6)

n = int(readline())
res = [0]*3

a = list(map(int,readline().split()))

mex = [[1,2,1],[2,0,0],[1,0,0]]

def brute(a):
    b = [0]*n
    b[0] = int(readline())
    for i in range(1,n):
        b[i] = mex[a[i]][b[i-1]]
    return b

if n <= 10:
    #print(a)
    for i in a: res[i] += 1
    for _ in range(n-1):
        a = brute(a)        
        for i in a: res[i] += 1
        #print(a)
    print(*res)    
    return


for _ in range(4):
    for i in a: res[i] += 1
    a = brute(a)

for i in range(3):
    res[a[i]] += 1

res[a[3]] += n-4
for i in range(4,n):
    res[a[i]] += n-i

b = a[:4]


for i in range(5,n):
    x = int(readline())
    b[0] = x
    for j in range(1,4):
        res[x] += 1
        x = mex[x][b[j]]
        b[j] = x
    
    #print(x)
    res[x] += n-i


print(*res)

mex = ((1,2,1),(2,0,0),(1,0,0))
"""
import random
a= [[random.randrange(0,3) for _ in range(10)] for _ in range(10)]
for i in range(3,10):
    for j in range(3,10):
        a[i][j] = mex[a[i-1][j]][a[i][j-1]]"""
#n=10
n=int(input())
*a1,=list(map(int, input().split()))
a=[a1]
for _ in range(n-1):
    a.append([int(input())])
ans=[0,0,0]
from copy import deepcopy
if n<20:
    for i in range(1,n):
        for j in range(1,n):
            a[i].append(mex[a[i-1][j]][a[i][j-1]])
    for i in range(n):
        for j in range(n):
            ans[a[i][j]]+=1
    print((*ans))
    return


for i in range(1,5):
    for j in range(1,n):
        a[i].append(mex[a[i-1][j]][a[i][j-1]])

for i in range(5,n):
    for j in range(1,5):
        a[i].append(mex[a[i-1][j]][a[i][j-1]])

for i in range(5):
    for j in range(n):
        ans[a[i][j]]+=1
        ans[a[j][i]]+=1

for i in range(5):
    for j in range(5):ans[a[i][j]]-=1


for j in range(4,n):
    ans[a[4][j]]+=n-j-1
    ans[a[j][4]]+=n-j-1
ans[a[4][4]]-=n-5
print((*ans))