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: VERY_HARD

Starter code:

Solutions:
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
counter = [0, 0, 0]
N = int(input())
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()))
	B = []
	for i in range(N - 1):
		B.append(int(input()))
	matrix = []
	matrix.append(A)
	for j in range(1, N):
		matrix.append([B[j - 1]])
	for i in range(1, 3):
		for j in range(1, N):
			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].append(mex(matrix[i - 1][j], matrix[i][j - 1]))
	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
	for i in range(3, 4):
		for j in range(3, N):
			matrix[i].append(mex(matrix[i - 1][j], matrix[i][j - 1]))
			counter[mex(matrix[i - 1][j], matrix[i][j - 1])] += N - j
	for i in range(4, N):
		for j in range(3, 4):
			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('{} {} {}'.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 >= 3 and j >= 3:
			A[a[i][j]] += n - max(i, j)
		else:
			A[a[i][j]] += 1
print(*A)


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())])
	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)


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)


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)


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:
	for i in a:
		res[i] += 1
	for _ in range(n - 1):
		a = brute(a)
		for i in a:
			res[i] += 1
	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
	res[x] += n - i
print(*res)