# -*- coding: utf-8 -*-
import copy
from collections import defaultdict
from itertools import product
FALL = '|'
RIVER = '~'
POOL = 'N'
SOURCE = 'x'
SOURCE_AND_FALL = '*'
SOURCE_AND_RIVER = 'X'
SOURCE_AND_POOL = '%'
BLOCK = '#'
LRAMP = '/'
RRAMP = '\\'
SPACE = ' '
LRAMP_AND_FALL = 'd'
RRAMP_AND_FALL = 'b'
LRAMP_AND_RIVER = '}'
RRAMP_AND_RIVER = '{'
LRAMP_AND_POOL = ']'
RRAMP_AND_POOL = '['
gridStr = """\
x
# #
# #
# #
#### #####
#### #####
#### #####
##########"""
gridStr = """\
x
# # #
# # #
# # #
# # #
# # #
#######################"""
gridStr = """\
x
# /
#####"""
gridStr = """\
x
# /
#####
# #
# # /
###\/#"""
gridStr = """\
x #
# # #
# # #
# # #
# #
######"""
HALF_CAPACITY = 50
MAX_CAPACITY = 2*HALF_CAPACITY
MAX_DOWN_RATE = HALF_CAPACITY
SOURCE_RATE = HALF_CAPACITY
DENSITY = 0.5
SPACE_THRESHHOLD = HALF_CAPACITY / 2
RIVER_THRESHHOLD = HALF_CAPACITY + HALF_CAPACITY / 2
def isSource(cell):
return cell in [SOURCE, SOURCE_AND_FALL, SOURCE_AND_RIVER, SOURCE_AND_POOL]
def isLRamp(cell):
return cell in [LRAMP, LRAMP_AND_FALL, LRAMP_AND_RIVER, LRAMP_AND_POOL]
def isRRamp(cell):
return cell in [RRAMP, RRAMP_AND_FALL, RRAMP_AND_RIVER, RRAMP_AND_POOL]
def isRamp(cell):
return isLRamp(cell) or isRRamp(cell)
def findBackground(cell):
if cell in [SPACE, FALL, RIVER, POOL, SOURCE]:
return SPACE
elif cell in [BLOCK]:
return BLOCK
elif isLRamp(cell):
return LRAMP
elif isRRamp(cell):
return RRAMP
raise Exception
class WaterType:
FALL = 1
SETTLED = 2
class Cell:
def __init__(self, background, isSource):
self.background = background
self.isSource = isSource
self.water = 0
self.waterType = WaterType.FALL
self.capacity = (0 if background == BLOCK else (HALF_CAPACITY if isRamp(background) else MAX_CAPACITY))
def copyCell(self, cell):
self.background = cell.background
self.capacity = cell.capacity
self.isSource = cell.isSource
# Include any water already here
self.water += cell.water
self.waterType = cell.waterType
def __str__(self):
if self.background == SPACE and not self.isSource and self.water <= SPACE_THRESHHOLD:
return SPACE
elif self.background == SPACE and not self.isSource and self.waterType == WaterType.FALL:
return FALL
elif self.background == SPACE and not self.isSource and self.water <= RIVER_THRESHHOLD:
return RIVER
elif self.background == SPACE and not self.isSource:
return POOL
elif self.background == SPACE and self.water <= SPACE_THRESHHOLD:
return SOURCE
elif self.background == SPACE and self.waterType == WaterType.FALL:
return SOURCE_AND_FALL
elif self.background == SPACE and self.water <= RIVER_THRESHHOLD:
return SOURCE_AND_RIVER
elif self.background == SPACE:
return SOURCE_AND_POOL
elif self.background == BLOCK:
return BLOCK
elif isRamp(self.background) and self.isSource:
raise Exception
elif self.background == LRAMP and self.water <= SPACE_THRESHHOLD / 2:
return LRAMP
elif self.background == LRAMP and self.waterType == WaterType.FALL:
return LRAMP_AND_FALL
elif self.background == LRAMP and self.water <= RIVER_THRESHHOLD / 2:
return LRAMP_AND_RIVER
elif self.background == LRAMP:
return LRAMP_AND_POOL
elif self.water <= SPACE_THRESHHOLD / 2:
return RRAMP
elif self.waterType == WaterType.FALL:
return RRAMP_AND_FALL
elif self.water <= RIVER_THRESHHOLD / 2:
return RRAMP_AND_RIVER
else:
return RRAMP_AND_POOL
gridCells = map(lambda x: list(x), gridStr.split('\n'))
height = len(gridCells)
width = len(gridCells[0])
grid = defaultdict(lambda : Cell(SPACE, False))
for i in range(height):
for j in range(width):
grid[i,j] = Cell(findBackground(gridCells[i][j]), isSource(gridCells[i][j]))
def findApatures(grid, i, j):
apature = {}
if grid[i,j].background == BLOCK:
apature[i-1,j] = apature[i+1,j] = apature[i,j-1] = apature[i,j+1] = 0
elif grid[i,j].background == LRAMP:
apature[i+1,j] = apature[i,j+1] = 0
apature[i-1,j] = 0 if grid[i-1,j].background in [BLOCK, LRAMP, RRAMP] else MAX_CAPACITY
apature[i,j-1] = 0 if grid[i,j-1].background in [BLOCK, LRAMP] else MAX_CAPACITY
elif grid[i,j].background == RRAMP:
apature[i+1,j] = apature[i,j-1] = 0
apature[i-1,j] = 0 if grid[i-1,j].background in [BLOCK, LRAMP, RRAMP] else MAX_CAPACITY
apature[i,j+1] = 0 if grid[i,j+1].background in [BLOCK, RRAMP] else MAX_CAPACITY
elif grid[i,j].background == SPACE:
apature[i-1,j] = 0 if grid[i-1,j].background in [BLOCK, LRAMP, RRAMP] else MAX_CAPACITY
apature[i+1,j] = 0 if grid[i+1,j].background in [BLOCK] else MAX_CAPACITY
apature[i,j-1] = 0 if grid[i,j-1].background in [BLOCK, LRAMP] else MAX_CAPACITY
apature[i,j+1] = 0 if grid[i,j+1].background in [BLOCK, RRAMP] else MAX_CAPACITY
else:
raise Exception
return apature
def displayGrid(grid):
print
for i in range(height):
row = ''
for j in range(width):
row += str(grid[i,j])
row += ' '
for j in range(width):
row += ('%x'%(grid[i,j].water / 10) if grid[i,j].water < 160 else '+')
print row
t = 0
while t < 50:
displayGrid(grid)
newGrid = defaultdict(lambda : Cell(SPACE, False))
for i, j in product(range(height), range(width)):
cell = grid[i,j]
newCell = newGrid[i,j]
newCell.copyCell(cell)
initWater = cell.water
water = cell.water
if cell.isSource:
water += SOURCE_RATE
apature = findApatures(grid, i, j)
# Downwards
availableFlow = min(max(grid[i+1,j].capacity - grid[i+1,j].water, 0), apature[i+1,j])
toMove = min(availableFlow, water, MAX_DOWN_RATE)
water -= toMove
newGrid[i+1,j].water += toMove
if toMove > 0:
newGrid[i,j].waterType = WaterType.FALL
else:
newGrid[i,j].waterType = WaterType.SETTLED
# Left and right
availableFlowLeft = min(max(grid[i,j-1].capacity - grid[i,j-1].water, 0), apature[i,j-1])
availableFlowRight = min(max(grid[i,j+1].capacity - grid[i,j+1].water, 0), apature[i,j+1])
if availableFlowLeft + availableFlowRight > 0:
spreadNumerator = (apature[i,j-1] + apature[i,j+1]) / MAX_CAPACITY
spreadDenominator = (apature[i,j-1] + apature[i,j+1] + cell.capacity) / MAX_CAPACITY
toMove = min(availableFlowLeft + availableFlowRight, int((water * spreadNumerator) / spreadDenominator))
toMoveLeft = int((toMove * availableFlowLeft) / (availableFlowLeft + availableFlowRight))
toMoveRight = int((toMove * availableFlowRight) / (availableFlowLeft + availableFlowRight))
water -= (toMoveLeft + toMoveRight)
newGrid[i,j-1].water += toMoveLeft
newGrid[i,j+1].water += toMoveRight
# Up
availableFlow = min(max(grid[i-1,j].capacity - grid[i-1,j].water, 0), apature[i-1,j])
if water > MAX_CAPACITY:
toMove = min(availableFlow, water - MAX_CAPACITY)
water -= toMove
newGrid[i-1,j].water += toMove
newGrid[i,j].water += (water - initWater)
grid = newGrid
t += 1
IyAtKi0gY29kaW5nOiB1dGYtOCAtKi0KaW1wb3J0IGNvcHkKZnJvbSBjb2xsZWN0aW9ucyBpbXBvcnQgZGVmYXVsdGRpY3QKZnJvbSBpdGVydG9vbHMgaW1wb3J0IHByb2R1Y3QKCkZBTEwgPSAnfCcKUklWRVIgPSAnficKUE9PTCA9ICdOJwogClNPVVJDRSA9ICd4JwpTT1VSQ0VfQU5EX0ZBTEwgPSAnKicKU09VUkNFX0FORF9SSVZFUiA9ICdYJwpTT1VSQ0VfQU5EX1BPT0wgPSAnJScKIApCTE9DSyA9ICcjJwpMUkFNUCA9ICcvJwpSUkFNUCA9ICdcXCcKU1BBQ0UgPSAnICcKIApMUkFNUF9BTkRfRkFMTCA9ICdkJwpSUkFNUF9BTkRfRkFMTCA9ICdiJwpMUkFNUF9BTkRfUklWRVIgPSAnfScKUlJBTVBfQU5EX1JJVkVSID0gJ3snCkxSQU1QX0FORF9QT09MID0gJ10nClJSQU1QX0FORF9QT09MID0gJ1snCgpncmlkU3RyID0gIiIiXAogICB4ICAgICAgCiMgICAgICAgICMKIyAgICAgICAgIwojICAgICAgICAjCiMjIyMgIyMjIyMKIyMjIyAjIyMjIwojIyMjICMjIyMjCiMjIyMjIyMjIyMiIiIKZ3JpZFN0ciA9ICIiIlwKICAgICAgICAgICAgICAgICAgICB4ICAKICAgICAgICAgICAgICAgICAgICAgICAKICAgICAgICAgICAgICAgICAgICAgICAKIyAgICAgICAgICAgICAgICAgICAjICMKIyAgICAgICAgICAgICAgICAgICAjICMKIyAgICAgICAgICAgICAgICAgICAjICMKIyAgICAgICAgICAgICAgICAgICAjICMKIyAgICAgICAgICAgICAgICAgICAjICMKIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMiIiIKZ3JpZFN0ciA9ICIiIlwKICB4ICAKIyAgLyAKIyMjIyMiIiIKZ3JpZFN0ciA9ICIiIlwKICB4ICAgCiMgICAvIAojIyMjIyAKIyAgICMgCiMgIyAgLwojIyNcLyMiIiIKZ3JpZFN0ciA9ICIiIlwKIHggIyAgCiMgICMgIwojICAjICMKIyAgIyAjCiMgICAgIwojIyMjIyMiIiIKCkhBTEZfQ0FQQUNJVFkgPSA1MApNQVhfQ0FQQUNJVFkgPSAyKkhBTEZfQ0FQQUNJVFkKTUFYX0RPV05fUkFURSA9IEhBTEZfQ0FQQUNJVFkKU09VUkNFX1JBVEUgPSBIQUxGX0NBUEFDSVRZCkRFTlNJVFkgPSAwLjUKClNQQUNFX1RIUkVTSEhPTEQgPSBIQUxGX0NBUEFDSVRZIC8gMgpSSVZFUl9USFJFU0hIT0xEID0gSEFMRl9DQVBBQ0lUWSArIEhBTEZfQ0FQQUNJVFkgLyAyCgpkZWYgaXNTb3VyY2UoY2VsbCk6CiAgICByZXR1cm4gY2VsbCBpbiBbU09VUkNFLCBTT1VSQ0VfQU5EX0ZBTEwsIFNPVVJDRV9BTkRfUklWRVIsIFNPVVJDRV9BTkRfUE9PTF0KCmRlZiBpc0xSYW1wKGNlbGwpOgogICAgcmV0dXJuIGNlbGwgaW4gW0xSQU1QLCBMUkFNUF9BTkRfRkFMTCwgTFJBTVBfQU5EX1JJVkVSLCBMUkFNUF9BTkRfUE9PTF0KZGVmIGlzUlJhbXAoY2VsbCk6CiAgICByZXR1cm4gY2VsbCBpbiBbUlJBTVAsIFJSQU1QX0FORF9GQUxMLCBSUkFNUF9BTkRfUklWRVIsIFJSQU1QX0FORF9QT09MXQpkZWYgaXNSYW1wKGNlbGwpOgogICAgcmV0dXJuIGlzTFJhbXAoY2VsbCkgb3IgaXNSUmFtcChjZWxsKQoKZGVmIGZpbmRCYWNrZ3JvdW5kKGNlbGwpOgogICAgaWYgY2VsbCBpbiBbU1BBQ0UsIEZBTEwsIFJJVkVSLCBQT09MLCBTT1VSQ0VdOgogICAgICAgIHJldHVybiBTUEFDRQogICAgZWxpZiBjZWxsIGluIFtCTE9DS106CiAgICAgICAgcmV0dXJuIEJMT0NLCiAgICBlbGlmIGlzTFJhbXAoY2VsbCk6CiAgICAgICAgcmV0dXJuIExSQU1QCiAgICBlbGlmIGlzUlJhbXAoY2VsbCk6CiAgICAgICAgcmV0dXJuIFJSQU1QCiAgICByYWlzZSBFeGNlcHRpb24KCmNsYXNzIFdhdGVyVHlwZToKICAgIEZBTEwgPSAxCiAgICBTRVRUTEVEID0gMgoKY2xhc3MgQ2VsbDoKICAgIGRlZiBfX2luaXRfXyhzZWxmLCBiYWNrZ3JvdW5kLCBpc1NvdXJjZSk6CiAgICAgICAgc2VsZi5iYWNrZ3JvdW5kID0gYmFja2dyb3VuZAogICAgICAgIHNlbGYuaXNTb3VyY2UgPSBpc1NvdXJjZQogICAgICAgIHNlbGYud2F0ZXIgPSAwCiAgICAgICAgc2VsZi53YXRlclR5cGUgPSBXYXRlclR5cGUuRkFMTAogICAgICAgIHNlbGYuY2FwYWNpdHkgPSAoMCBpZiBiYWNrZ3JvdW5kID09IEJMT0NLIGVsc2UgKEhBTEZfQ0FQQUNJVFkgaWYgaXNSYW1wKGJhY2tncm91bmQpIGVsc2UgTUFYX0NBUEFDSVRZKSkKICAgIGRlZiBjb3B5Q2VsbChzZWxmLCBjZWxsKToKICAgICAgICBzZWxmLmJhY2tncm91bmQgPSBjZWxsLmJhY2tncm91bmQKICAgICAgICBzZWxmLmNhcGFjaXR5ID0gY2VsbC5jYXBhY2l0eQogICAgICAgIHNlbGYuaXNTb3VyY2UgPSBjZWxsLmlzU291cmNlCiAgICAgICAgIyBJbmNsdWRlIGFueSB3YXRlciBhbHJlYWR5IGhlcmUKICAgICAgICBzZWxmLndhdGVyICs9IGNlbGwud2F0ZXIKICAgICAgICBzZWxmLndhdGVyVHlwZSA9IGNlbGwud2F0ZXJUeXBlCiAgICBkZWYgX19zdHJfXyhzZWxmKToKICAgICAgICBpZiBzZWxmLmJhY2tncm91bmQgPT0gU1BBQ0UgYW5kIG5vdCBzZWxmLmlzU291cmNlIGFuZCBzZWxmLndhdGVyIDw9IFNQQUNFX1RIUkVTSEhPTEQ6CiAgICAgICAgICAgIHJldHVybiBTUEFDRQogICAgICAgIGVsaWYgc2VsZi5iYWNrZ3JvdW5kID09IFNQQUNFIGFuZCBub3Qgc2VsZi5pc1NvdXJjZSBhbmQgc2VsZi53YXRlclR5cGUgPT0gV2F0ZXJUeXBlLkZBTEw6CiAgICAgICAgICAgIHJldHVybiBGQUxMCiAgICAgICAgZWxpZiBzZWxmLmJhY2tncm91bmQgPT0gU1BBQ0UgYW5kIG5vdCBzZWxmLmlzU291cmNlIGFuZCBzZWxmLndhdGVyIDw9IFJJVkVSX1RIUkVTSEhPTEQ6CiAgICAgICAgICAgIHJldHVybiBSSVZFUgogICAgICAgIGVsaWYgc2VsZi5iYWNrZ3JvdW5kID09IFNQQUNFIGFuZCBub3Qgc2VsZi5pc1NvdXJjZToKICAgICAgICAgICAgcmV0dXJuIFBPT0wKICAgICAgICBlbGlmIHNlbGYuYmFja2dyb3VuZCA9PSBTUEFDRSBhbmQgc2VsZi53YXRlciA8PSBTUEFDRV9USFJFU0hIT0xEOgogICAgICAgICAgICByZXR1cm4gU09VUkNFCiAgICAgICAgZWxpZiBzZWxmLmJhY2tncm91bmQgPT0gU1BBQ0UgYW5kIHNlbGYud2F0ZXJUeXBlID09IFdhdGVyVHlwZS5GQUxMOgogICAgICAgICAgICByZXR1cm4gU09VUkNFX0FORF9GQUxMCiAgICAgICAgZWxpZiBzZWxmLmJhY2tncm91bmQgPT0gU1BBQ0UgYW5kIHNlbGYud2F0ZXIgPD0gUklWRVJfVEhSRVNISE9MRDoKICAgICAgICAgICAgcmV0dXJuIFNPVVJDRV9BTkRfUklWRVIKICAgICAgICBlbGlmIHNlbGYuYmFja2dyb3VuZCA9PSBTUEFDRToKICAgICAgICAgICAgcmV0dXJuIFNPVVJDRV9BTkRfUE9PTAogICAgICAgIGVsaWYgc2VsZi5iYWNrZ3JvdW5kID09IEJMT0NLOgogICAgICAgICAgICByZXR1cm4gQkxPQ0sKICAgICAgICBlbGlmIGlzUmFtcChzZWxmLmJhY2tncm91bmQpIGFuZCBzZWxmLmlzU291cmNlOgogICAgICAgICAgICByYWlzZSBFeGNlcHRpb24KICAgICAgICBlbGlmIHNlbGYuYmFja2dyb3VuZCA9PSBMUkFNUCBhbmQgc2VsZi53YXRlciA8PSBTUEFDRV9USFJFU0hIT0xEIC8gMjoKICAgICAgICAgICAgcmV0dXJuIExSQU1QCiAgICAgICAgZWxpZiBzZWxmLmJhY2tncm91bmQgPT0gTFJBTVAgYW5kIHNlbGYud2F0ZXJUeXBlID09IFdhdGVyVHlwZS5GQUxMOgogICAgICAgICAgICByZXR1cm4gTFJBTVBfQU5EX0ZBTEwKICAgICAgICBlbGlmIHNlbGYuYmFja2dyb3VuZCA9PSBMUkFNUCBhbmQgc2VsZi53YXRlciA8PSBSSVZFUl9USFJFU0hIT0xEIC8gMjoKICAgICAgICAgICAgcmV0dXJuIExSQU1QX0FORF9SSVZFUgogICAgICAgIGVsaWYgc2VsZi5iYWNrZ3JvdW5kID09IExSQU1QOgogICAgICAgICAgICByZXR1cm4gTFJBTVBfQU5EX1BPT0wKICAgICAgICBlbGlmIHNlbGYud2F0ZXIgPD0gU1BBQ0VfVEhSRVNISE9MRCAvIDI6CiAgICAgICAgICAgIHJldHVybiBSUkFNUAogICAgICAgIGVsaWYgc2VsZi53YXRlclR5cGUgPT0gV2F0ZXJUeXBlLkZBTEw6CiAgICAgICAgICAgIHJldHVybiBSUkFNUF9BTkRfRkFMTAogICAgICAgIGVsaWYgc2VsZi53YXRlciA8PSBSSVZFUl9USFJFU0hIT0xEIC8gMjoKICAgICAgICAgICAgcmV0dXJuIFJSQU1QX0FORF9SSVZFUgogICAgICAgIGVsc2U6CiAgICAgICAgICAgIHJldHVybiBSUkFNUF9BTkRfUE9PTAoKZ3JpZENlbGxzID0gbWFwKGxhbWJkYSB4OiBsaXN0KHgpLCBncmlkU3RyLnNwbGl0KCdcbicpKQpoZWlnaHQgPSBsZW4oZ3JpZENlbGxzKQp3aWR0aCA9IGxlbihncmlkQ2VsbHNbMF0pCmdyaWQgPSBkZWZhdWx0ZGljdChsYW1iZGEgOiBDZWxsKFNQQUNFLCBGYWxzZSkpCmZvciBpIGluIHJhbmdlKGhlaWdodCk6CiAgICBmb3IgaiBpbiByYW5nZSh3aWR0aCk6CiAgICAgICAgZ3JpZFtpLGpdID0gQ2VsbChmaW5kQmFja2dyb3VuZChncmlkQ2VsbHNbaV1bal0pLCBpc1NvdXJjZShncmlkQ2VsbHNbaV1bal0pKQogICAgICAgIApkZWYgZmluZEFwYXR1cmVzKGdyaWQsIGksIGopOgogICAgYXBhdHVyZSA9IHt9CiAgICBpZiBncmlkW2ksal0uYmFja2dyb3VuZCA9PSBCTE9DSzoKICAgICAgICBhcGF0dXJlW2ktMSxqXSA9IGFwYXR1cmVbaSsxLGpdID0gYXBhdHVyZVtpLGotMV0gPSBhcGF0dXJlW2ksaisxXSA9IDAKICAgIGVsaWYgZ3JpZFtpLGpdLmJhY2tncm91bmQgPT0gTFJBTVA6CiAgICAgICAgYXBhdHVyZVtpKzEsal0gPSBhcGF0dXJlW2ksaisxXSA9IDAKICAgICAgICBhcGF0dXJlW2ktMSxqXSA9IDAgaWYgZ3JpZFtpLTEsal0uYmFja2dyb3VuZCBpbiBbQkxPQ0ssIExSQU1QLCBSUkFNUF0gZWxzZSBNQVhfQ0FQQUNJVFkKICAgICAgICBhcGF0dXJlW2ksai0xXSA9IDAgaWYgZ3JpZFtpLGotMV0uYmFja2dyb3VuZCBpbiBbQkxPQ0ssIExSQU1QXSBlbHNlIE1BWF9DQVBBQ0lUWQogICAgZWxpZiBncmlkW2ksal0uYmFja2dyb3VuZCA9PSBSUkFNUDoKICAgICAgICBhcGF0dXJlW2krMSxqXSA9IGFwYXR1cmVbaSxqLTFdID0gMAogICAgICAgIGFwYXR1cmVbaS0xLGpdID0gMCBpZiBncmlkW2ktMSxqXS5iYWNrZ3JvdW5kIGluIFtCTE9DSywgTFJBTVAsIFJSQU1QXSBlbHNlIE1BWF9DQVBBQ0lUWQogICAgICAgIGFwYXR1cmVbaSxqKzFdID0gMCBpZiBncmlkW2ksaisxXS5iYWNrZ3JvdW5kIGluIFtCTE9DSywgUlJBTVBdIGVsc2UgTUFYX0NBUEFDSVRZCiAgICBlbGlmIGdyaWRbaSxqXS5iYWNrZ3JvdW5kID09IFNQQUNFOgogICAgICAgIGFwYXR1cmVbaS0xLGpdID0gMCBpZiBncmlkW2ktMSxqXS5iYWNrZ3JvdW5kIGluIFtCTE9DSywgTFJBTVAsIFJSQU1QXSBlbHNlIE1BWF9DQVBBQ0lUWQogICAgICAgIGFwYXR1cmVbaSsxLGpdID0gMCBpZiBncmlkW2krMSxqXS5iYWNrZ3JvdW5kIGluIFtCTE9DS10gZWxzZSBNQVhfQ0FQQUNJVFkKICAgICAgICBhcGF0dXJlW2ksai0xXSA9IDAgaWYgZ3JpZFtpLGotMV0uYmFja2dyb3VuZCBpbiBbQkxPQ0ssIExSQU1QXSBlbHNlIE1BWF9DQVBBQ0lUWQogICAgICAgIGFwYXR1cmVbaSxqKzFdID0gMCBpZiBncmlkW2ksaisxXS5iYWNrZ3JvdW5kIGluIFtCTE9DSywgUlJBTVBdIGVsc2UgTUFYX0NBUEFDSVRZCiAgICBlbHNlOgogICAgICAgIHJhaXNlIEV4Y2VwdGlvbgogICAgcmV0dXJuIGFwYXR1cmUKCmRlZiBkaXNwbGF5R3JpZChncmlkKToKICAgIHByaW50CiAgICBmb3IgaSBpbiByYW5nZShoZWlnaHQpOgogICAgICAgIHJvdyA9ICcnCiAgICAgICAgZm9yIGogaW4gcmFuZ2Uod2lkdGgpOgogICAgICAgICAgICByb3cgKz0gc3RyKGdyaWRbaSxqXSkKICAgICAgICByb3cgKz0gJyAnCiAgICAgICAgZm9yIGogaW4gcmFuZ2Uod2lkdGgpOgogICAgICAgICAgICByb3cgKz0gKCcleCclKGdyaWRbaSxqXS53YXRlciAvIDEwKSBpZiBncmlkW2ksal0ud2F0ZXIgPCAxNjAgZWxzZSAnKycpCiAgICAgICAgcHJpbnQgcm93CiAKdCA9IDAKd2hpbGUgdCA8IDUwOgogICAgZGlzcGxheUdyaWQoZ3JpZCkKICAgIG5ld0dyaWQgPSBkZWZhdWx0ZGljdChsYW1iZGEgOiBDZWxsKFNQQUNFLCBGYWxzZSkpCiAgICBmb3IgaSwgaiBpbiBwcm9kdWN0KHJhbmdlKGhlaWdodCksIHJhbmdlKHdpZHRoKSk6CiAgICAgICAgY2VsbCA9IGdyaWRbaSxqXQogICAgICAgIG5ld0NlbGwgPSBuZXdHcmlkW2ksal0KICAgICAgICBuZXdDZWxsLmNvcHlDZWxsKGNlbGwpCiAgICAgICAgaW5pdFdhdGVyID0gY2VsbC53YXRlcgogICAgICAgIHdhdGVyID0gY2VsbC53YXRlcgogICAgICAgIGlmIGNlbGwuaXNTb3VyY2U6CiAgICAgICAgICAgIHdhdGVyICs9IFNPVVJDRV9SQVRFCiAgICAgICAgYXBhdHVyZSA9IGZpbmRBcGF0dXJlcyhncmlkLCBpLCBqKQogICAgICAgICMgRG93bndhcmRzCiAgICAgICAgYXZhaWxhYmxlRmxvdyA9IG1pbihtYXgoZ3JpZFtpKzEsal0uY2FwYWNpdHkgLSBncmlkW2krMSxqXS53YXRlciwgMCksIGFwYXR1cmVbaSsxLGpdKQogICAgICAgIHRvTW92ZSA9IG1pbihhdmFpbGFibGVGbG93LCB3YXRlciwgTUFYX0RPV05fUkFURSkKICAgICAgICB3YXRlciAtPSB0b01vdmUKICAgICAgICBuZXdHcmlkW2krMSxqXS53YXRlciArPSB0b01vdmUKICAgICAgICBpZiB0b01vdmUgPiAwOgogICAgICAgICAgICBuZXdHcmlkW2ksal0ud2F0ZXJUeXBlID0gV2F0ZXJUeXBlLkZBTEwKICAgICAgICBlbHNlOgogICAgICAgICAgICBuZXdHcmlkW2ksal0ud2F0ZXJUeXBlID0gV2F0ZXJUeXBlLlNFVFRMRUQKICAgICAgICAjIExlZnQgYW5kIHJpZ2h0CiAgICAgICAgYXZhaWxhYmxlRmxvd0xlZnQgPSBtaW4obWF4KGdyaWRbaSxqLTFdLmNhcGFjaXR5IC0gZ3JpZFtpLGotMV0ud2F0ZXIsIDApLCBhcGF0dXJlW2ksai0xXSkKICAgICAgICBhdmFpbGFibGVGbG93UmlnaHQgPSBtaW4obWF4KGdyaWRbaSxqKzFdLmNhcGFjaXR5IC0gZ3JpZFtpLGorMV0ud2F0ZXIsIDApLCBhcGF0dXJlW2ksaisxXSkKICAgICAgICBpZiBhdmFpbGFibGVGbG93TGVmdCArIGF2YWlsYWJsZUZsb3dSaWdodCA+IDA6CiAgICAgICAgICAgIHNwcmVhZE51bWVyYXRvciA9IChhcGF0dXJlW2ksai0xXSArIGFwYXR1cmVbaSxqKzFdKSAvIE1BWF9DQVBBQ0lUWSAgICAgICAgCiAgICAgICAgICAgIHNwcmVhZERlbm9taW5hdG9yID0gKGFwYXR1cmVbaSxqLTFdICsgYXBhdHVyZVtpLGorMV0gKyBjZWxsLmNhcGFjaXR5KSAvIE1BWF9DQVBBQ0lUWQogICAgICAgICAgICB0b01vdmUgPSBtaW4oYXZhaWxhYmxlRmxvd0xlZnQgKyBhdmFpbGFibGVGbG93UmlnaHQsIGludCgod2F0ZXIgKiBzcHJlYWROdW1lcmF0b3IpIC8gc3ByZWFkRGVub21pbmF0b3IpKQogICAgICAgICAgICB0b01vdmVMZWZ0ID0gaW50KCh0b01vdmUgKiBhdmFpbGFibGVGbG93TGVmdCkgLyAoYXZhaWxhYmxlRmxvd0xlZnQgKyBhdmFpbGFibGVGbG93UmlnaHQpKQogICAgICAgICAgICB0b01vdmVSaWdodCA9IGludCgodG9Nb3ZlICogYXZhaWxhYmxlRmxvd1JpZ2h0KSAvIChhdmFpbGFibGVGbG93TGVmdCArIGF2YWlsYWJsZUZsb3dSaWdodCkpCiAgICAgICAgICAgIHdhdGVyIC09ICh0b01vdmVMZWZ0ICsgdG9Nb3ZlUmlnaHQpCiAgICAgICAgICAgIG5ld0dyaWRbaSxqLTFdLndhdGVyICs9IHRvTW92ZUxlZnQKICAgICAgICAgICAgbmV3R3JpZFtpLGorMV0ud2F0ZXIgKz0gdG9Nb3ZlUmlnaHQKICAgICAgICAjIFVwCiAgICAgICAgYXZhaWxhYmxlRmxvdyA9IG1pbihtYXgoZ3JpZFtpLTEsal0uY2FwYWNpdHkgLSBncmlkW2ktMSxqXS53YXRlciwgMCksIGFwYXR1cmVbaS0xLGpdKQogICAgICAgIGlmIHdhdGVyID4gTUFYX0NBUEFDSVRZOgogICAgICAgICAgICB0b01vdmUgPSBtaW4oYXZhaWxhYmxlRmxvdywgd2F0ZXIgLSBNQVhfQ0FQQUNJVFkpCiAgICAgICAgICAgIHdhdGVyIC09IHRvTW92ZQogICAgICAgICAgICBuZXdHcmlkW2ktMSxqXS53YXRlciArPSB0b01vdmUKICAgICAgICBuZXdHcmlkW2ksal0ud2F0ZXIgKz0gKHdhdGVyIC0gaW5pdFdhdGVyKQogICAgZ3JpZCA9IG5ld0dyaWQKICAgIHQgKz0gMQoKCgoKCgoKCgoKCgoKCgoKCgogICAgICAgIA==