# Lakota East High School (7070)

# Senior-3 division

# 2005-06, round 2

# Ross Wang

# Language = Python

import sys

def parseLine(line):

return [int(n) for n in line if n >= "0" and n <= "9"]

def buildGrid(grid2D):

return [[[[grid2D[3 * x + z][3 * w + y]

for z in range(3)]

for y in range(3)]

for x in range(3)]

for w in range(3)]

def readGrid(fin):

return buildGrid([parseLine(fin.readline()) for line in range(9)])

def analyzeGeneral(grid4D, ci1, cc1, ci2, cc2, vi1, vi2):

digits = range(1, 10)

coords = [0] * 4

coords[ci1] = cc1

coords[ci2] = cc2

for coords[vi1] in range(3):

for coords[vi2] in range(3):

val = grid4D[coords[0]][coords[1]][coords[2]][coords[3]]

if val in digits:

digits.remove(val)

return digits

def analyzeRow(grid4D, x, z):

return analyzeGeneral(grid4D, 1, x, 3, z, 0, 2)

def analyzeCol(grid4D, w, y):

return analyzeGeneral(grid4D, 0, w, 2, y, 1, 3)

def analyzeSqr(grid4D, w, x):

return analyzeGeneral(grid4D, 0, w, 1, x, 3, 2)

def fullAnalyze(grid4D, cell):

rowResult = analyzeRow(grid4D, cell[1], cell[3])

colResult = analyzeCol(grid4D, cell[0], cell[2])

sqrResult = analyzeSqr(grid4D, cell[0], cell[1])

return [a for a in

[b for b in rowResult

if b in colResult]

if a in sqrResult]

def solveGeneral(grid4D, cells):

while len(cells):

retry = list()

for cell in cells:

sln = fullAnalyze(grid4D, cell)

if len(sln) == 0:

return False #fail

elif len(sln) == 1:

grid4D[cell[0]][cell[1]][cell[2]][cell[3]] = sln[0]

else:

retry.append(cell)

if cells == retry: #stagnant

return False #fail

cells = retry

return True

def solveRow(grid4D, x, z):

return solveGeneral(grid4D, [(w, x, y, z)

for w in range(3)

for y in range(3)

if grid4D[w][x][y][z] == 0])

def fullSolve(grid4D):

return solveGeneral(grid4D, [(w, x, y, z)

for w in range(3)

for x in range(3)

for y in range(3)

for z in range(3)

if grid4D[w][x][y][z] == 0])

def solveACSL(grid4D, row):

row -= 1 #1-based

z = row % 3

x = row / 3

if not solveRow(grid4D, x, z):

fullSolve(grid4D) #cannot just solve this row

return "".join([str(grid4D[w][x][y][z])

for w in range(3)

for y in range(3)])

def doACSL():

grid = readGrid(sys.stdin)

for x in range(5):

print solveACSL(grid, int(sys.stdin.readline()))

doACSL()