# -*- coding: utf-8 -*-
import copy
from collections import defaultdict
from itertools import product
import heapq
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 = '['
DOWN = (1,0)
LEFT = (0,-1)
RIGHT = (0,1)
UP = (-1,0)
ORDINALS = [DOWN,LEFT,RIGHT,UP]
gridStr = """\
x
# #
# #
# #
#### #####
#### #####
#### #####
##########"""
gridStr = """\
x
# /
#####
# #
# # /
###\/#"""
gridStr = """\
x
# /
#####"""
gridStr = """\
x
# # #
# # #
# # #
# # #
# # #
#######################"""
gridStr = """\
x #
# # #
# # #
# # #
# #
######"""
# The capacity of a ramp cell.
HALF_CAPACITY = 50
# The capacity of an empty cell.
MAX_CAPACITY = 2*HALF_CAPACITY
# The rate of flow in from a source.
SOURCE_RATE = HALF_CAPACITY
# The maximum rate of flow between two cells.
MAX_FLOW = MAX_CAPACITY
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
def getCapacity(self):
return (0 if self.background == BLOCK else (HALF_CAPACITY if isRamp(self.background) else MAX_CAPACITY))
def copyCell(self, cell):
self.background = cell.background
self.isSource = cell.isSource
# Include any water already here
self.water += cell.water
self.waterType = cell.waterType
def updateType(self, cellBelow):
if self.water == 0:
self.waterType = WaterType.SETTLED
elif self.water == self.getCapacity():
# If a completely saturated block of water is falling it should still look full.
self.waterType = WaterType.SETTLED
elif cellBelow.water < cellBelow.getCapacity():
self.waterType = WaterType.FALL
else:
self.waterType = WaterType.SETTLED
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 p(coords, offset):
"""Add two tuples together.
>>> p((2, 3), (-1, 0))
(1, 3)
"""
return tuple(map(sum, zip(coords, offset)))
def adjacent(i,j,includeUp):
ret = []
for offset in (ORDINALS if includeUp else ORDINALS[:-1]):
ret.append(p((i,j), offset))
return ret
CONNECTION_TO_SHAPES = {DOWN: [SPACE, LRAMP, RRAMP], LEFT: [SPACE, RRAMP], RIGHT: [SPACE, LRAMP], UP: [SPACE]}
def adjoint(grid, i, j, includeUp, includeDown):
"""Find all cells connected to this one (if this is a block then nothing connects to it).
>>> grid = defaultdict(lambda : Cell(SPACE, False))
>>> adjoint(grid, 10, 1, True, True)
[(11, 1), (10, 0), (10, 2), (9, 1)]
>>> adjoint(grid, 10, 1, False, True)
[(11, 1), (10, 0), (10, 2)]
>>> adjoint(grid, 10, 1, False, False)
[(10, 0), (10, 2)]
>>> grid[10, 1].background = LRAMP
>>> adjoint(grid, 10, 1, True, True)
[(10, 0), (9, 1)]
>>> grid[10, 0].background = LRAMP
>>> grid[9, 1].background = RRAMP
>>> adjoint(grid, 10, 1, True, True)
[]
"""
ret = []
cell = grid[i, j]
if cell.background == BLOCK:
adj = []
elif cell.background == LRAMP:
adj = [LEFT, UP]
elif cell.background == RRAMP:
adj = [RIGHT, UP]
elif cell.background == SPACE:
adj = list(ORDINALS)
if not includeUp and UP in adj:
adj.remove(UP)
if not includeDown and DOWN in adj:
adj.remove(DOWN)
for offset in adj:
neighbourCoords = p((i,j), offset)
neighbour = grid[neighbourCoords]
if neighbour.background in CONNECTION_TO_SHAPES[offset]:
ret.append(neighbourCoords)
return ret
def distance(loc1, loc2):
"""Calculate the manhatten distance between two locations.
>>> distance((5,2), (3, 1))
3
"""
row1, col1 = loc1
row2, col2 = loc2
d_col = abs(col1 - col2)
d_row = abs(row1 - row2)
return d_row + d_col
def aStarRegion(start, end, region, edge):
"""The AStar algorithm to find the shortest path between two cells using the region as the nodes, and the edges in edge.
>>> grid = defaultdict(lambda : Cell(SPACE, False))
>>> edge = defaultdict(dict)
>>> edge[1,0] = {(1,1): 1}
>>> edge[1,1] = {(2,1): 1}
>>> aStarRegion((1,0), (2,1), [(1,0),(1,1),(2,1)], edge)
[(1, 0), (1, 1), (2, 1)]
"""
openSet = set()
openHeap = []
closedSet = set()
parent = {}
def retracePath(c, edge):
path = [c]
while c in parent:
c = parent[c]
path.append(c)
path.reverse()
return path
current = start
openSet.add(current)
openHeap.append((0,current))
while openSet:
current = heapq.heappop(openHeap)[1]
if current == end:
return retracePath(current, edge)
openSet.remove(current)
closedSet.add(current)
for tile, remainingFlow in edge[current].items():
if tile not in closedSet:
H = distance(tile, end)*10
if tile not in openSet:
openSet.add(tile)
heapq.heappush(openHeap, (H,tile))
parent[tile] = current
return []
def findWaterRegions(grid, height, width):
"""Find water regions. Return a dict keyed on the top left (top then left) cell of each region.
>>> grid = defaultdict(lambda : Cell(SPACE, False))
>>> waterRegions, outlets, edges = findWaterRegions(grid, 4, 5)
>>> waterRegions
{}
>>> outlets
{}
>>> dict(edges)
{}
>>> grid[2,2].water = MAX_CAPACITY
>>> grid[2,3].water = MAX_CAPACITY
>>> grid[3,3].water = MAX_CAPACITY
>>> waterRegions, outlets, edges = findWaterRegions(grid, 4, 5)
>>> waterRegions
{(2, 2): [(2, 2), (2, 3), (3, 3)]}
>>> outlets
{(2, 2): [(3, 2), (2, 1), (1, 2), (2, 4), (1, 3), (4, 3), (3, 2), (3, 4)]}
>>> dict(edges)
{(2, 2): defaultdict(<type 'dict'>, {(2, 3): {(2, 4): 100, (1, 3): 100, (3, 3): 100, (2, 2): 100}, (3, 3): {(2, 3): 100, (3, 2): 100, (3, 4): 100, (4, 3): 100}, (2, 2): {(1, 2): 100, (3, 2): 100, (2, 3): 100, (2, 1): 100}})}
>>> grid[2,3].background = LRAMP
>>> grid[2,3].water = HALF_CAPACITY
>>> waterRegions, outlets, edges = findWaterRegions(grid, 4, 5)
>>> waterRegions
{(3, 3): [(3, 3)], (2, 2): [(2, 2), (2, 3)]}
>>> outlets
{(3, 3): [(4, 3), (3, 2), (3, 4)], (2, 2): [(3, 2), (2, 1), (1, 2), (1, 3)]}
>>> dict(edges)
{(3, 3): defaultdict(<type 'dict'>, {(3, 3): {(3, 2): 100, (3, 4): 100, (4, 3): 100}}), (2, 2): defaultdict(<type 'dict'>, {(2, 3): {(1, 3): 100, (2, 2): 100}, (2, 2): {(1, 2): 100, (3, 2): 100, (2, 3): 100, (2, 1): 100}})}
>>> grid = defaultdict(lambda : Cell(SPACE, False))
>>> grid[2,3].background = LRAMP
>>> grid[2,3].water = HALF_CAPACITY - 1
>>> waterRegions, outlets, edges = findWaterRegions(grid, 4, 5)
>>> waterRegions
{(2, 3): [(2, 3)]}
>>> outlets
{(2, 3): [(2, 3), (2, 2)]}
>>> dict(edges)
{(2, 3): defaultdict(<type 'dict'>, {(2, 3): {(2, 2): 100}})}
>>> grid = defaultdict(lambda : Cell(SPACE, False))
>>> grid[1,0].background = BLOCK
>>> grid[1,4].background = BLOCK
>>> grid[2,0].background = BLOCK
>>> grid[2,4].background = BLOCK
>>> grid[3,1].background = RRAMP
>>> grid[4,2].background = BLOCK
>>> grid[2,2].background = BLOCK
>>> grid[3,3].background = LRAMP
>>> grid[3,1].water = HALF_CAPACITY
>>> grid[3,2].water = MAX_CAPACITY
>>> grid[3,3].water = HALF_CAPACITY
>>> waterRegions, outlets, edges = findWaterRegions(grid, 4, 5)
>>> waterRegions
{(3, 1): [(3, 1), (3, 2), (3, 3)]}
>>> outlets
{(3, 1): [(2, 1), (2, 3)]}
>>> dict(edges)
{(3, 1): defaultdict(<type 'dict'>, {(3, 2): {(3, 1): 100, (3, 3): 100}, (3, 1): {(3, 2): 100, (2, 1): 100}, (3, 3): {(3, 2): 100, (2, 3): 100}})}
>>> grid = defaultdict(lambda : Cell(SPACE, False))
>>> grid[0,0].water = MAX_CAPACITY - 1
>>> grid[1,0].water = MAX_CAPACITY - 1
>>> waterRegions, outlets, edges = findWaterRegions(grid, 4, 5)
>>> waterRegions
{(1, 0): [(1, 0)], (0, 0): [(0, 0)]}
>>> outlets
{(1, 0): [(1, 0), (2, 0), (1, -1), (1, 1)], (0, 0): [(0, 0), (1, 0), (0, -1), (0, 1)]}
>>> dict(edges)
{(1, 0): defaultdict(<type 'dict'>, {(1, 0): {(2, 0): 100, (1, -1): 100, (1, 1): 100}}), (0, 0): defaultdict(<type 'dict'>, {(0, 0): {(0, 1): 100, (0, -1): 100, (1, 0): 100}})}
"""
waterRegions = {}
outlets = {}
edges = defaultdict(lambda : defaultdict(dict))
explored = []
for i, j in product(range(height), range(width)):
if (i,j) not in explored:
cell = grid[i,j]
if cell.water > 0:
waterRegions[i,j] = [(i,j)]
outlets[i,j] = ([] if grid[i,j].water == grid[i,j].getCapacity() else [(i,j)])
toExplore = [(i,j)]
while len(toExplore) > 0:
hereX, hereY = toExplore.pop()
explored.append((hereX, hereY))
includeUp = (grid[hereX,hereY].water == grid[hereX,hereY].getCapacity())
includeDown = (grid[hereX+1,hereY].water == grid[hereX+1,hereY].getCapacity())
for x, y in adjoint(grid, hereX, hereY, includeUp, includeDown):
if grid[x,y].water != 0 and (x,y) not in explored:
toExplore.append((x,y))
waterRegions[i,j].append((x,y))
for x, y in adjoint(grid, hereX, hereY, includeUp, True):
edges[i,j][hereX,hereY][x,y] = MAX_FLOW
if grid[x,y].water != grid[x,y].getCapacity():
outlets[i,j].append((x,y))
return waterRegions, outlets, edges
def findHeight(grid, point):
return (height - point[0]) * MAX_CAPACITY + grid[point].water
def findHighestPoint(grid, region):
highestPoint = region[0]
highestHeight = findHeight(grid, highestPoint)
for point in region:
height = findHeight(grid, point)
if height > highestHeight:
highestHeight = height
highestPoint = point
return highestPoint
def findLowestPoint(grid, region):
lowestPoint = region[0]
lowestHeight = findHeight(grid, lowestPoint)
for point in region:
height = findHeight(grid, point)
if height < lowestHeight:
lowestHeight = height
lowestPoint = point
return lowestPoint
def moveWater(grid, start, end, region, edge):
"""Move a unit of water from start to end. Return True if successful."""
path = aStarRegion(start, end, region, edge)
if len(path) == 0:
return False
grid[start].water -= 1
stepStart = start
for stepEnd in path[1:]:
edge[stepStart][stepEnd] -= 1
if edge[stepStart][stepEnd] == 0:
edge[stepStart].pop(stepEnd)
if len(edge[stepStart]) == 0:
edge.pop(stepStart)
stepStart = stepEnd
grid[end].water += 1
return True
def displayGrid(grid):
print
for i in range(height):
row = ''
for j in range(width):
grid[i,j].updateType(grid[i+1,j])
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
def main(grid):
t = 0
while t < 20:
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)
if cell.isSource:
newCell.water += SOURCE_RATE
grid = newGrid
waterRegions, outlets, edges = findWaterRegions(grid, height, width)
movedSomething = True
while movedSomething:
movedSomething = False
for regionKey in waterRegions.keys():
waterRegion = waterRegions[regionKey]
outlet = outlets[regionKey]
edge = edges[regionKey]
start = findHighestPoint(grid, waterRegion)
end = findLowestPoint(grid, outlet)
if findHeight(grid, start) > findHeight(grid, end):
movedSomething = moveWater(grid, start, end, waterRegion + [end], edge)
if grid[start].water == 0:
waterRegion.remove(start)
if len(waterRegion) == 0:
waterRegions.pop(regionKey)
t += 1
if __name__ == '__main__':
import doctest
# Doesn't test inner functions!
failures, passes = doctest.testmod(raise_on_error=False)
if failures == 0:
main(grid)
else:
print 'Stopping with %d failures'%failures
IyAtKi0gY29kaW5nOiB1dGYtOCAtKi0KaW1wb3J0IGNvcHkKZnJvbSBjb2xsZWN0aW9ucyBpbXBvcnQgZGVmYXVsdGRpY3QKZnJvbSBpdGVydG9vbHMgaW1wb3J0IHByb2R1Y3QKaW1wb3J0IGhlYXBxCgpGQUxMID0gJ3wnClJJVkVSID0gJ34nClBPT0wgPSAnTicKIApTT1VSQ0UgPSAneCcKU09VUkNFX0FORF9GQUxMID0gJyonClNPVVJDRV9BTkRfUklWRVIgPSAnWCcKU09VUkNFX0FORF9QT09MID0gJyUnCiAKQkxPQ0sgPSAnIycKTFJBTVAgPSAnLycKUlJBTVAgPSAnXFwnClNQQUNFID0gJyAnCiAKTFJBTVBfQU5EX0ZBTEwgPSAnZCcKUlJBTVBfQU5EX0ZBTEwgPSAnYicKTFJBTVBfQU5EX1JJVkVSID0gJ30nClJSQU1QX0FORF9SSVZFUiA9ICd7JwpMUkFNUF9BTkRfUE9PTCA9ICddJwpSUkFNUF9BTkRfUE9PTCA9ICdbJwoKRE9XTiA9ICgxLDApCkxFRlQgPSAoMCwtMSkKUklHSFQgPSAoMCwxKQpVUCA9ICgtMSwwKQpPUkRJTkFMUyA9IFtET1dOLExFRlQsUklHSFQsVVBdCgpncmlkU3RyID0gIiIiXAogICB4ICAgICAgCiMgICAgICAgICMKIyAgICAgICAgIwojICAgICAgICAjCiMjIyMgIyMjIyMKIyMjIyAjIyMjIwojIyMjICMjIyMjCiMjIyMjIyMjIyMiIiIKZ3JpZFN0ciA9ICIiIlwKICB4ICAgCiMgICAvIAojIyMjIyAKIyAgICMgCiMgIyAgLwojIyNcLyMiIiIKZ3JpZFN0ciA9ICIiIlwKICB4ICAKIyAgLyAKIyMjIyMiIiIKZ3JpZFN0ciA9ICIiIlwKICAgICAgICAgICAgICAgICAgICB4ICAKICAgICAgICAgICAgICAgICAgICAgICAKICAgICAgICAgICAgICAgICAgICAgICAKIyAgICAgICAgICAgICAgICAgICAjICMKIyAgICAgICAgICAgICAgICAgICAjICMKIyAgICAgICAgICAgICAgICAgICAjICMKIyAgICAgICAgICAgICAgICAgICAjICMKIyAgICAgICAgICAgICAgICAgICAjICMKIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMiIiIKZ3JpZFN0ciA9ICIiIlwKIHggIyAgCiMgICMgIwojICAjICMKIyAgIyAjCiMgICAgIwojIyMjIyMiIiIKCiMgVGhlIGNhcGFjaXR5IG9mIGEgcmFtcCBjZWxsLgpIQUxGX0NBUEFDSVRZID0gNTAKIyBUaGUgY2FwYWNpdHkgb2YgYW4gZW1wdHkgY2VsbC4KTUFYX0NBUEFDSVRZID0gMipIQUxGX0NBUEFDSVRZCiMgVGhlIHJhdGUgb2YgZmxvdyBpbiBmcm9tIGEgc291cmNlLgpTT1VSQ0VfUkFURSA9IEhBTEZfQ0FQQUNJVFkKIyBUaGUgbWF4aW11bSByYXRlIG9mIGZsb3cgYmV0d2VlbiB0d28gY2VsbHMuCk1BWF9GTE9XID0gTUFYX0NBUEFDSVRZCgpTUEFDRV9USFJFU0hIT0xEID0gSEFMRl9DQVBBQ0lUWSAvIDIKUklWRVJfVEhSRVNISE9MRCA9IEhBTEZfQ0FQQUNJVFkgKyBIQUxGX0NBUEFDSVRZIC8gMgoKZGVmIGlzU291cmNlKGNlbGwpOgogICAgcmV0dXJuIGNlbGwgaW4gW1NPVVJDRSwgU09VUkNFX0FORF9GQUxMLCBTT1VSQ0VfQU5EX1JJVkVSLCBTT1VSQ0VfQU5EX1BPT0xdCgpkZWYgaXNMUmFtcChjZWxsKToKICAgIHJldHVybiBjZWxsIGluIFtMUkFNUCwgTFJBTVBfQU5EX0ZBTEwsIExSQU1QX0FORF9SSVZFUiwgTFJBTVBfQU5EX1BPT0xdCmRlZiBpc1JSYW1wKGNlbGwpOgogICAgcmV0dXJuIGNlbGwgaW4gW1JSQU1QLCBSUkFNUF9BTkRfRkFMTCwgUlJBTVBfQU5EX1JJVkVSLCBSUkFNUF9BTkRfUE9PTF0KZGVmIGlzUmFtcChjZWxsKToKICAgIHJldHVybiBpc0xSYW1wKGNlbGwpIG9yIGlzUlJhbXAoY2VsbCkKCmRlZiBmaW5kQmFja2dyb3VuZChjZWxsKToKICAgIGlmIGNlbGwgaW4gW1NQQUNFLCBGQUxMLCBSSVZFUiwgUE9PTCwgU09VUkNFXToKICAgICAgICByZXR1cm4gU1BBQ0UKICAgIGVsaWYgY2VsbCBpbiBbQkxPQ0tdOgogICAgICAgIHJldHVybiBCTE9DSwogICAgZWxpZiBpc0xSYW1wKGNlbGwpOgogICAgICAgIHJldHVybiBMUkFNUAogICAgZWxpZiBpc1JSYW1wKGNlbGwpOgogICAgICAgIHJldHVybiBSUkFNUAogICAgcmFpc2UgRXhjZXB0aW9uCgpjbGFzcyBXYXRlclR5cGU6CiAgICBGQUxMID0gMQogICAgU0VUVExFRCA9IDIKCmNsYXNzIENlbGw6CiAgICBkZWYgX19pbml0X18oc2VsZiwgYmFja2dyb3VuZCwgaXNTb3VyY2UpOgogICAgICAgIHNlbGYuYmFja2dyb3VuZCA9IGJhY2tncm91bmQKICAgICAgICBzZWxmLmlzU291cmNlID0gaXNTb3VyY2UKICAgICAgICBzZWxmLndhdGVyID0gMAogICAgICAgIHNlbGYud2F0ZXJUeXBlID0gV2F0ZXJUeXBlLkZBTEwKICAgIGRlZiBnZXRDYXBhY2l0eShzZWxmKToKICAgICAgICByZXR1cm4gKDAgaWYgc2VsZi5iYWNrZ3JvdW5kID09IEJMT0NLIGVsc2UgKEhBTEZfQ0FQQUNJVFkgaWYgaXNSYW1wKHNlbGYuYmFja2dyb3VuZCkgZWxzZSBNQVhfQ0FQQUNJVFkpKQogICAgZGVmIGNvcHlDZWxsKHNlbGYsIGNlbGwpOgogICAgICAgIHNlbGYuYmFja2dyb3VuZCA9IGNlbGwuYmFja2dyb3VuZAogICAgICAgIHNlbGYuaXNTb3VyY2UgPSBjZWxsLmlzU291cmNlCiAgICAgICAgIyBJbmNsdWRlIGFueSB3YXRlciBhbHJlYWR5IGhlcmUKICAgICAgICBzZWxmLndhdGVyICs9IGNlbGwud2F0ZXIKICAgICAgICBzZWxmLndhdGVyVHlwZSA9IGNlbGwud2F0ZXJUeXBlCiAgICBkZWYgdXBkYXRlVHlwZShzZWxmLCBjZWxsQmVsb3cpOgogICAgICAgIGlmIHNlbGYud2F0ZXIgPT0gMDoKICAgICAgICAgICAgc2VsZi53YXRlclR5cGUgPSBXYXRlclR5cGUuU0VUVExFRAogICAgICAgIGVsaWYgc2VsZi53YXRlciA9PSBzZWxmLmdldENhcGFjaXR5KCk6CiAgICAgICAgICAgICMgSWYgYSBjb21wbGV0ZWx5IHNhdHVyYXRlZCBibG9jayBvZiB3YXRlciBpcyBmYWxsaW5nIGl0IHNob3VsZCBzdGlsbCBsb29rIGZ1bGwuCiAgICAgICAgICAgIHNlbGYud2F0ZXJUeXBlID0gV2F0ZXJUeXBlLlNFVFRMRUQKICAgICAgICBlbGlmIGNlbGxCZWxvdy53YXRlciA8IGNlbGxCZWxvdy5nZXRDYXBhY2l0eSgpOgogICAgICAgICAgICBzZWxmLndhdGVyVHlwZSA9IFdhdGVyVHlwZS5GQUxMCiAgICAgICAgZWxzZToKICAgICAgICAgICAgc2VsZi53YXRlclR5cGUgPSBXYXRlclR5cGUuU0VUVExFRAogICAgZGVmIF9fc3RyX18oc2VsZik6CiAgICAgICAgaWYgc2VsZi5iYWNrZ3JvdW5kID09IFNQQUNFIGFuZCBub3Qgc2VsZi5pc1NvdXJjZSBhbmQgc2VsZi53YXRlciA8PSBTUEFDRV9USFJFU0hIT0xEOgogICAgICAgICAgICByZXR1cm4gU1BBQ0UKICAgICAgICBlbGlmIHNlbGYuYmFja2dyb3VuZCA9PSBTUEFDRSBhbmQgbm90IHNlbGYuaXNTb3VyY2UgYW5kIHNlbGYud2F0ZXJUeXBlID09IFdhdGVyVHlwZS5GQUxMOgogICAgICAgICAgICByZXR1cm4gRkFMTAogICAgICAgIGVsaWYgc2VsZi5iYWNrZ3JvdW5kID09IFNQQUNFIGFuZCBub3Qgc2VsZi5pc1NvdXJjZSBhbmQgc2VsZi53YXRlciA8PSBSSVZFUl9USFJFU0hIT0xEOgogICAgICAgICAgICByZXR1cm4gUklWRVIKICAgICAgICBlbGlmIHNlbGYuYmFja2dyb3VuZCA9PSBTUEFDRSBhbmQgbm90IHNlbGYuaXNTb3VyY2U6CiAgICAgICAgICAgIHJldHVybiBQT09MCiAgICAgICAgZWxpZiBzZWxmLmJhY2tncm91bmQgPT0gU1BBQ0UgYW5kIHNlbGYud2F0ZXIgPD0gU1BBQ0VfVEhSRVNISE9MRDoKICAgICAgICAgICAgcmV0dXJuIFNPVVJDRQogICAgICAgIGVsaWYgc2VsZi5iYWNrZ3JvdW5kID09IFNQQUNFIGFuZCBzZWxmLndhdGVyVHlwZSA9PSBXYXRlclR5cGUuRkFMTDoKICAgICAgICAgICAgcmV0dXJuIFNPVVJDRV9BTkRfRkFMTAogICAgICAgIGVsaWYgc2VsZi5iYWNrZ3JvdW5kID09IFNQQUNFIGFuZCBzZWxmLndhdGVyIDw9IFJJVkVSX1RIUkVTSEhPTEQ6CiAgICAgICAgICAgIHJldHVybiBTT1VSQ0VfQU5EX1JJVkVSCiAgICAgICAgZWxpZiBzZWxmLmJhY2tncm91bmQgPT0gU1BBQ0U6CiAgICAgICAgICAgIHJldHVybiBTT1VSQ0VfQU5EX1BPT0wKICAgICAgICBlbGlmIHNlbGYuYmFja2dyb3VuZCA9PSBCTE9DSzoKICAgICAgICAgICAgcmV0dXJuIEJMT0NLCiAgICAgICAgZWxpZiBpc1JhbXAoc2VsZi5iYWNrZ3JvdW5kKSBhbmQgc2VsZi5pc1NvdXJjZToKICAgICAgICAgICAgcmFpc2UgRXhjZXB0aW9uCiAgICAgICAgZWxpZiBzZWxmLmJhY2tncm91bmQgPT0gTFJBTVAgYW5kIHNlbGYud2F0ZXIgPD0gU1BBQ0VfVEhSRVNISE9MRCAvIDI6CiAgICAgICAgICAgIHJldHVybiBMUkFNUAogICAgICAgIGVsaWYgc2VsZi5iYWNrZ3JvdW5kID09IExSQU1QIGFuZCBzZWxmLndhdGVyVHlwZSA9PSBXYXRlclR5cGUuRkFMTDoKICAgICAgICAgICAgcmV0dXJuIExSQU1QX0FORF9GQUxMCiAgICAgICAgZWxpZiBzZWxmLmJhY2tncm91bmQgPT0gTFJBTVAgYW5kIHNlbGYud2F0ZXIgPD0gUklWRVJfVEhSRVNISE9MRCAvIDI6CiAgICAgICAgICAgIHJldHVybiBMUkFNUF9BTkRfUklWRVIKICAgICAgICBlbGlmIHNlbGYuYmFja2dyb3VuZCA9PSBMUkFNUDoKICAgICAgICAgICAgcmV0dXJuIExSQU1QX0FORF9QT09MCiAgICAgICAgZWxpZiBzZWxmLndhdGVyIDw9IFNQQUNFX1RIUkVTSEhPTEQgLyAyOgogICAgICAgICAgICByZXR1cm4gUlJBTVAKICAgICAgICBlbGlmIHNlbGYud2F0ZXJUeXBlID09IFdhdGVyVHlwZS5GQUxMOgogICAgICAgICAgICByZXR1cm4gUlJBTVBfQU5EX0ZBTEwKICAgICAgICBlbGlmIHNlbGYud2F0ZXIgPD0gUklWRVJfVEhSRVNISE9MRCAvIDI6CiAgICAgICAgICAgIHJldHVybiBSUkFNUF9BTkRfUklWRVIKICAgICAgICBlbHNlOgogICAgICAgICAgICByZXR1cm4gUlJBTVBfQU5EX1BPT0wKCmdyaWRDZWxscyA9IG1hcChsYW1iZGEgeDogbGlzdCh4KSwgZ3JpZFN0ci5zcGxpdCgnXG4nKSkKaGVpZ2h0ID0gbGVuKGdyaWRDZWxscykKd2lkdGggPSBsZW4oZ3JpZENlbGxzWzBdKQpncmlkID0gZGVmYXVsdGRpY3QobGFtYmRhIDogQ2VsbChTUEFDRSwgRmFsc2UpKQpmb3IgaSBpbiByYW5nZShoZWlnaHQpOgogICAgZm9yIGogaW4gcmFuZ2Uod2lkdGgpOgogICAgICAgIGdyaWRbaSxqXSA9IENlbGwoZmluZEJhY2tncm91bmQoZ3JpZENlbGxzW2ldW2pdKSwgaXNTb3VyY2UoZ3JpZENlbGxzW2ldW2pdKSkKCmRlZiBwKGNvb3Jkcywgb2Zmc2V0KToKICAgICIiIkFkZCB0d28gdHVwbGVzIHRvZ2V0aGVyLgogICAgCiAgICA+Pj4gcCgoMiwgMyksICgtMSwgMCkpCiAgICAoMSwgMykKICAgICIiIgogICAgcmV0dXJuIHR1cGxlKG1hcChzdW0sIHppcChjb29yZHMsIG9mZnNldCkpKQoKZGVmIGFkamFjZW50KGksaixpbmNsdWRlVXApOgogICAgcmV0ID0gW10KICAgIGZvciBvZmZzZXQgaW4gKE9SRElOQUxTIGlmIGluY2x1ZGVVcCBlbHNlIE9SRElOQUxTWzotMV0pOgogICAgICAgIHJldC5hcHBlbmQocCgoaSxqKSwgb2Zmc2V0KSkKICAgIHJldHVybiByZXQKCkNPTk5FQ1RJT05fVE9fU0hBUEVTID0ge0RPV046IFtTUEFDRSwgTFJBTVAsIFJSQU1QXSwgTEVGVDogW1NQQUNFLCBSUkFNUF0sIFJJR0hUOiBbU1BBQ0UsIExSQU1QXSwgVVA6IFtTUEFDRV19CgpkZWYgYWRqb2ludChncmlkLCBpLCBqLCBpbmNsdWRlVXAsIGluY2x1ZGVEb3duKToKICAgICIiIkZpbmQgYWxsIGNlbGxzIGNvbm5lY3RlZCB0byB0aGlzIG9uZSAoaWYgdGhpcyBpcyBhIGJsb2NrIHRoZW4gbm90aGluZyBjb25uZWN0cyB0byBpdCkuCiAgICAKICAgID4+PiBncmlkID0gZGVmYXVsdGRpY3QobGFtYmRhIDogQ2VsbChTUEFDRSwgRmFsc2UpKQogICAgPj4+IGFkam9pbnQoZ3JpZCwgMTAsIDEsIFRydWUsIFRydWUpCiAgICBbKDExLCAxKSwgKDEwLCAwKSwgKDEwLCAyKSwgKDksIDEpXQogICAgCiAgICA+Pj4gYWRqb2ludChncmlkLCAxMCwgMSwgRmFsc2UsIFRydWUpCiAgICBbKDExLCAxKSwgKDEwLCAwKSwgKDEwLCAyKV0KICAgIAogICAgPj4+IGFkam9pbnQoZ3JpZCwgMTAsIDEsIEZhbHNlLCBGYWxzZSkKICAgIFsoMTAsIDApLCAoMTAsIDIpXQogICAgCiAgICA+Pj4gZ3JpZFsxMCwgMV0uYmFja2dyb3VuZCA9IExSQU1QCiAgICA+Pj4gYWRqb2ludChncmlkLCAxMCwgMSwgVHJ1ZSwgVHJ1ZSkKICAgIFsoMTAsIDApLCAoOSwgMSldCiAgICAKICAgID4+PiBncmlkWzEwLCAwXS5iYWNrZ3JvdW5kID0gTFJBTVAKICAgID4+PiBncmlkWzksIDFdLmJhY2tncm91bmQgPSBSUkFNUAogICAgPj4+IGFkam9pbnQoZ3JpZCwgMTAsIDEsIFRydWUsIFRydWUpCiAgICBbXQogICAgIiIiCiAgICByZXQgPSBbXQogICAgY2VsbCA9IGdyaWRbaSwgal0KICAgIGlmIGNlbGwuYmFja2dyb3VuZCA9PSBCTE9DSzoKICAgICAgICBhZGogPSBbXQogICAgZWxpZiBjZWxsLmJhY2tncm91bmQgPT0gTFJBTVA6CiAgICAgICAgYWRqID0gW0xFRlQsIFVQXQogICAgZWxpZiBjZWxsLmJhY2tncm91bmQgPT0gUlJBTVA6CiAgICAgICAgYWRqID0gW1JJR0hULCBVUF0KICAgIGVsaWYgY2VsbC5iYWNrZ3JvdW5kID09IFNQQUNFOgogICAgICAgIGFkaiA9IGxpc3QoT1JESU5BTFMpCiAgICBpZiBub3QgaW5jbHVkZVVwIGFuZCBVUCBpbiBhZGo6CiAgICAgICAgYWRqLnJlbW92ZShVUCkKICAgIGlmIG5vdCBpbmNsdWRlRG93biBhbmQgRE9XTiBpbiBhZGo6CiAgICAgICAgYWRqLnJlbW92ZShET1dOKQogICAgZm9yIG9mZnNldCBpbiBhZGo6CiAgICAgICAgbmVpZ2hib3VyQ29vcmRzID0gcCgoaSxqKSwgb2Zmc2V0KQogICAgICAgIG5laWdoYm91ciA9IGdyaWRbbmVpZ2hib3VyQ29vcmRzXQogICAgICAgIGlmIG5laWdoYm91ci5iYWNrZ3JvdW5kIGluIENPTk5FQ1RJT05fVE9fU0hBUEVTW29mZnNldF06CiAgICAgICAgICAgIHJldC5hcHBlbmQobmVpZ2hib3VyQ29vcmRzKQogICAgcmV0dXJuIHJldAoKZGVmIGRpc3RhbmNlKGxvYzEsIGxvYzIpOgogICAgIiIiQ2FsY3VsYXRlIHRoZSBtYW5oYXR0ZW4gZGlzdGFuY2UgYmV0d2VlbiB0d28gbG9jYXRpb25zLgogICAgCiAgICA+Pj4gZGlzdGFuY2UoKDUsMiksICgzLCAxKSkKICAgIDMKICAgICIiIgogICAgcm93MSwgY29sMSA9IGxvYzEKICAgIHJvdzIsIGNvbDIgPSBsb2MyCiAgICBkX2NvbCA9IGFicyhjb2wxIC0gY29sMikKICAgIGRfcm93ID0gYWJzKHJvdzEgLSByb3cyKQogICAgcmV0dXJuIGRfcm93ICsgZF9jb2wKCmRlZiBhU3RhclJlZ2lvbihzdGFydCwgZW5kLCByZWdpb24sIGVkZ2UpOgogICAgIiIiVGhlIEFTdGFyIGFsZ29yaXRobSB0byBmaW5kIHRoZSBzaG9ydGVzdCBwYXRoIGJldHdlZW4gdHdvIGNlbGxzIHVzaW5nIHRoZSByZWdpb24gYXMgdGhlIG5vZGVzLCBhbmQgdGhlIGVkZ2VzIGluIGVkZ2UuCiAgICAKICAgID4+PiBncmlkID0gZGVmYXVsdGRpY3QobGFtYmRhIDogQ2VsbChTUEFDRSwgRmFsc2UpKQogICAgPj4+IGVkZ2UgPSBkZWZhdWx0ZGljdChkaWN0KQogICAgPj4+IGVkZ2VbMSwwXSA9IHsoMSwxKTogMX0KICAgID4+PiBlZGdlWzEsMV0gPSB7KDIsMSk6IDF9CiAgICA+Pj4gYVN0YXJSZWdpb24oKDEsMCksICgyLDEpLCBbKDEsMCksKDEsMSksKDIsMSldLCBlZGdlKQogICAgWygxLCAwKSwgKDEsIDEpLCAoMiwgMSldCiAgICAiIiIKICAgIG9wZW5TZXQgPSBzZXQoKQogICAgb3BlbkhlYXAgPSBbXQogICAgY2xvc2VkU2V0ID0gc2V0KCkKICAgIHBhcmVudCA9IHt9CgogICAgZGVmIHJldHJhY2VQYXRoKGMsIGVkZ2UpOgogICAgICAgIHBhdGggPSBbY10KICAgICAgICB3aGlsZSBjIGluIHBhcmVudDoKICAgICAgICAgICAgYyA9IHBhcmVudFtjXQogICAgICAgICAgICBwYXRoLmFwcGVuZChjKQogICAgICAgIHBhdGgucmV2ZXJzZSgpCiAgICAgICAgcmV0dXJuIHBhdGgKCiAgICBjdXJyZW50ID0gc3RhcnQKICAgIG9wZW5TZXQuYWRkKGN1cnJlbnQpCiAgICBvcGVuSGVhcC5hcHBlbmQoKDAsY3VycmVudCkpCiAgICB3aGlsZSBvcGVuU2V0OgogICAgICAgIGN1cnJlbnQgPSBoZWFwcS5oZWFwcG9wKG9wZW5IZWFwKVsxXQogICAgICAgIGlmIGN1cnJlbnQgPT0gZW5kOgogICAgICAgICAgICByZXR1cm4gcmV0cmFjZVBhdGgoY3VycmVudCwgZWRnZSkKICAgICAgICBvcGVuU2V0LnJlbW92ZShjdXJyZW50KQogICAgICAgIGNsb3NlZFNldC5hZGQoY3VycmVudCkKICAgICAgICBmb3IgdGlsZSwgcmVtYWluaW5nRmxvdyBpbiBlZGdlW2N1cnJlbnRdLml0ZW1zKCk6CiAgICAgICAgICAgIGlmIHRpbGUgbm90IGluIGNsb3NlZFNldDoKICAgICAgICAgICAgICAgIEggPSBkaXN0YW5jZSh0aWxlLCBlbmQpKjEwCiAgICAgICAgICAgICAgICBpZiB0aWxlIG5vdCBpbiBvcGVuU2V0OgogICAgICAgICAgICAgICAgICAgIG9wZW5TZXQuYWRkKHRpbGUpCiAgICAgICAgICAgICAgICAgICAgaGVhcHEuaGVhcHB1c2gob3BlbkhlYXAsIChILHRpbGUpKQogICAgICAgICAgICAgICAgcGFyZW50W3RpbGVdID0gY3VycmVudAogICAgcmV0dXJuIFtdCgpkZWYgZmluZFdhdGVyUmVnaW9ucyhncmlkLCBoZWlnaHQsIHdpZHRoKToKICAgICIiIkZpbmQgd2F0ZXIgcmVnaW9ucy4gUmV0dXJuIGEgZGljdCBrZXllZCBvbiB0aGUgdG9wIGxlZnQgKHRvcCB0aGVuIGxlZnQpIGNlbGwgb2YgZWFjaCByZWdpb24uCiAgICAKICAgID4+PiBncmlkID0gZGVmYXVsdGRpY3QobGFtYmRhIDogQ2VsbChTUEFDRSwgRmFsc2UpKQogICAgPj4+IHdhdGVyUmVnaW9ucywgb3V0bGV0cywgZWRnZXMgPSBmaW5kV2F0ZXJSZWdpb25zKGdyaWQsIDQsIDUpCiAgICA+Pj4gd2F0ZXJSZWdpb25zCiAgICB7fQogICAgPj4+IG91dGxldHMKICAgIHt9CiAgICA+Pj4gZGljdChlZGdlcykKICAgIHt9CiAgICAKICAgID4+PiBncmlkWzIsMl0ud2F0ZXIgPSBNQVhfQ0FQQUNJVFkKICAgID4+PiBncmlkWzIsM10ud2F0ZXIgPSBNQVhfQ0FQQUNJVFkKICAgID4+PiBncmlkWzMsM10ud2F0ZXIgPSBNQVhfQ0FQQUNJVFkKICAgID4+PiB3YXRlclJlZ2lvbnMsIG91dGxldHMsIGVkZ2VzID0gZmluZFdhdGVyUmVnaW9ucyhncmlkLCA0LCA1KQogICAgPj4+IHdhdGVyUmVnaW9ucwogICAgeygyLCAyKTogWygyLCAyKSwgKDIsIDMpLCAoMywgMyldfQogICAgPj4+IG91dGxldHMKICAgIHsoMiwgMik6IFsoMywgMiksICgyLCAxKSwgKDEsIDIpLCAoMiwgNCksICgxLCAzKSwgKDQsIDMpLCAoMywgMiksICgzLCA0KV19CiAgICA+Pj4gZGljdChlZGdlcykKICAgIHsoMiwgMik6IGRlZmF1bHRkaWN0KDx0eXBlICdkaWN0Jz4sIHsoMiwgMyk6IHsoMiwgNCk6IDEwMCwgKDEsIDMpOiAxMDAsICgzLCAzKTogMTAwLCAoMiwgMik6IDEwMH0sICgzLCAzKTogeygyLCAzKTogMTAwLCAoMywgMik6IDEwMCwgKDMsIDQpOiAxMDAsICg0LCAzKTogMTAwfSwgKDIsIDIpOiB7KDEsIDIpOiAxMDAsICgzLCAyKTogMTAwLCAoMiwgMyk6IDEwMCwgKDIsIDEpOiAxMDB9fSl9CiAgICAKICAgID4+PiBncmlkWzIsM10uYmFja2dyb3VuZCA9IExSQU1QCiAgICA+Pj4gZ3JpZFsyLDNdLndhdGVyID0gSEFMRl9DQVBBQ0lUWQogICAgPj4+IHdhdGVyUmVnaW9ucywgb3V0bGV0cywgZWRnZXMgPSBmaW5kV2F0ZXJSZWdpb25zKGdyaWQsIDQsIDUpCiAgICA+Pj4gd2F0ZXJSZWdpb25zCiAgICB7KDMsIDMpOiBbKDMsIDMpXSwgKDIsIDIpOiBbKDIsIDIpLCAoMiwgMyldfQogICAgPj4+IG91dGxldHMKICAgIHsoMywgMyk6IFsoNCwgMyksICgzLCAyKSwgKDMsIDQpXSwgKDIsIDIpOiBbKDMsIDIpLCAoMiwgMSksICgxLCAyKSwgKDEsIDMpXX0KICAgID4+PiBkaWN0KGVkZ2VzKQogICAgeygzLCAzKTogZGVmYXVsdGRpY3QoPHR5cGUgJ2RpY3QnPiwgeygzLCAzKTogeygzLCAyKTogMTAwLCAoMywgNCk6IDEwMCwgKDQsIDMpOiAxMDB9fSksICgyLCAyKTogZGVmYXVsdGRpY3QoPHR5cGUgJ2RpY3QnPiwgeygyLCAzKTogeygxLCAzKTogMTAwLCAoMiwgMik6IDEwMH0sICgyLCAyKTogeygxLCAyKTogMTAwLCAoMywgMik6IDEwMCwgKDIsIDMpOiAxMDAsICgyLCAxKTogMTAwfX0pfQogICAgCiAgICA+Pj4gZ3JpZCA9IGRlZmF1bHRkaWN0KGxhbWJkYSA6IENlbGwoU1BBQ0UsIEZhbHNlKSkKICAgID4+PiBncmlkWzIsM10uYmFja2dyb3VuZCA9IExSQU1QCiAgICA+Pj4gZ3JpZFsyLDNdLndhdGVyID0gSEFMRl9DQVBBQ0lUWSAtIDEKICAgID4+PiB3YXRlclJlZ2lvbnMsIG91dGxldHMsIGVkZ2VzID0gZmluZFdhdGVyUmVnaW9ucyhncmlkLCA0LCA1KQogICAgPj4+IHdhdGVyUmVnaW9ucwogICAgeygyLCAzKTogWygyLCAzKV19CiAgICA+Pj4gb3V0bGV0cwogICAgeygyLCAzKTogWygyLCAzKSwgKDIsIDIpXX0KICAgID4+PiBkaWN0KGVkZ2VzKQogICAgeygyLCAzKTogZGVmYXVsdGRpY3QoPHR5cGUgJ2RpY3QnPiwgeygyLCAzKTogeygyLCAyKTogMTAwfX0pfQogICAgCiAgICA+Pj4gZ3JpZCA9IGRlZmF1bHRkaWN0KGxhbWJkYSA6IENlbGwoU1BBQ0UsIEZhbHNlKSkKICAgID4+PiBncmlkWzEsMF0uYmFja2dyb3VuZCA9IEJMT0NLCiAgICA+Pj4gZ3JpZFsxLDRdLmJhY2tncm91bmQgPSBCTE9DSwogICAgPj4+IGdyaWRbMiwwXS5iYWNrZ3JvdW5kID0gQkxPQ0sKICAgID4+PiBncmlkWzIsNF0uYmFja2dyb3VuZCA9IEJMT0NLCiAgICA+Pj4gZ3JpZFszLDFdLmJhY2tncm91bmQgPSBSUkFNUAogICAgPj4+IGdyaWRbNCwyXS5iYWNrZ3JvdW5kID0gQkxPQ0sKICAgID4+PiBncmlkWzIsMl0uYmFja2dyb3VuZCA9IEJMT0NLCiAgICA+Pj4gZ3JpZFszLDNdLmJhY2tncm91bmQgPSBMUkFNUAogICAgPj4+IGdyaWRbMywxXS53YXRlciA9IEhBTEZfQ0FQQUNJVFkKICAgID4+PiBncmlkWzMsMl0ud2F0ZXIgPSBNQVhfQ0FQQUNJVFkKICAgID4+PiBncmlkWzMsM10ud2F0ZXIgPSBIQUxGX0NBUEFDSVRZCiAgICA+Pj4gd2F0ZXJSZWdpb25zLCBvdXRsZXRzLCBlZGdlcyA9IGZpbmRXYXRlclJlZ2lvbnMoZ3JpZCwgNCwgNSkKICAgID4+PiB3YXRlclJlZ2lvbnMKICAgIHsoMywgMSk6IFsoMywgMSksICgzLCAyKSwgKDMsIDMpXX0KICAgID4+PiBvdXRsZXRzCiAgICB7KDMsIDEpOiBbKDIsIDEpLCAoMiwgMyldfQogICAgPj4+IGRpY3QoZWRnZXMpCiAgICB7KDMsIDEpOiBkZWZhdWx0ZGljdCg8dHlwZSAnZGljdCc+LCB7KDMsIDIpOiB7KDMsIDEpOiAxMDAsICgzLCAzKTogMTAwfSwgKDMsIDEpOiB7KDMsIDIpOiAxMDAsICgyLCAxKTogMTAwfSwgKDMsIDMpOiB7KDMsIDIpOiAxMDAsICgyLCAzKTogMTAwfX0pfQogICAgCiAgICA+Pj4gZ3JpZCA9IGRlZmF1bHRkaWN0KGxhbWJkYSA6IENlbGwoU1BBQ0UsIEZhbHNlKSkKICAgID4+PiBncmlkWzAsMF0ud2F0ZXIgPSBNQVhfQ0FQQUNJVFkgLSAxCiAgICA+Pj4gZ3JpZFsxLDBdLndhdGVyID0gTUFYX0NBUEFDSVRZIC0gMQogICAgPj4+IHdhdGVyUmVnaW9ucywgb3V0bGV0cywgZWRnZXMgPSBmaW5kV2F0ZXJSZWdpb25zKGdyaWQsIDQsIDUpCiAgICA+Pj4gd2F0ZXJSZWdpb25zCiAgICB7KDEsIDApOiBbKDEsIDApXSwgKDAsIDApOiBbKDAsIDApXX0KICAgID4+PiBvdXRsZXRzCiAgICB7KDEsIDApOiBbKDEsIDApLCAoMiwgMCksICgxLCAtMSksICgxLCAxKV0sICgwLCAwKTogWygwLCAwKSwgKDEsIDApLCAoMCwgLTEpLCAoMCwgMSldfQogICAgPj4+IGRpY3QoZWRnZXMpCiAgICB7KDEsIDApOiBkZWZhdWx0ZGljdCg8dHlwZSAnZGljdCc+LCB7KDEsIDApOiB7KDIsIDApOiAxMDAsICgxLCAtMSk6IDEwMCwgKDEsIDEpOiAxMDB9fSksICgwLCAwKTogZGVmYXVsdGRpY3QoPHR5cGUgJ2RpY3QnPiwgeygwLCAwKTogeygwLCAxKTogMTAwLCAoMCwgLTEpOiAxMDAsICgxLCAwKTogMTAwfX0pfQogICAgIiIiCiAgICB3YXRlclJlZ2lvbnMgPSB7fQogICAgb3V0bGV0cyA9IHt9CiAgICBlZGdlcyA9IGRlZmF1bHRkaWN0KGxhbWJkYSA6IGRlZmF1bHRkaWN0KGRpY3QpKQogICAgZXhwbG9yZWQgPSBbXQogICAgZm9yIGksIGogaW4gcHJvZHVjdChyYW5nZShoZWlnaHQpLCByYW5nZSh3aWR0aCkpOgogICAgICAgIGlmIChpLGopIG5vdCBpbiBleHBsb3JlZDoKICAgICAgICAgICAgY2VsbCA9IGdyaWRbaSxqXQogICAgICAgICAgICBpZiBjZWxsLndhdGVyID4gMDoKICAgICAgICAgICAgICAgIHdhdGVyUmVnaW9uc1tpLGpdID0gWyhpLGopXQogICAgICAgICAgICAgICAgb3V0bGV0c1tpLGpdID0gKFtdIGlmIGdyaWRbaSxqXS53YXRlciA9PSBncmlkW2ksal0uZ2V0Q2FwYWNpdHkoKSBlbHNlIFsoaSxqKV0pCiAgICAgICAgICAgICAgICB0b0V4cGxvcmUgPSBbKGksaildCiAgICAgICAgICAgICAgICB3aGlsZSBsZW4odG9FeHBsb3JlKSA+IDA6CiAgICAgICAgICAgICAgICAgICAgaGVyZVgsIGhlcmVZID0gdG9FeHBsb3JlLnBvcCgpCiAgICAgICAgICAgICAgICAgICAgZXhwbG9yZWQuYXBwZW5kKChoZXJlWCwgaGVyZVkpKQogICAgICAgICAgICAgICAgICAgIGluY2x1ZGVVcCA9IChncmlkW2hlcmVYLGhlcmVZXS53YXRlciA9PSBncmlkW2hlcmVYLGhlcmVZXS5nZXRDYXBhY2l0eSgpKQogICAgICAgICAgICAgICAgICAgIGluY2x1ZGVEb3duID0gKGdyaWRbaGVyZVgrMSxoZXJlWV0ud2F0ZXIgPT0gZ3JpZFtoZXJlWCsxLGhlcmVZXS5nZXRDYXBhY2l0eSgpKQogICAgICAgICAgICAgICAgICAgIGZvciB4LCB5IGluIGFkam9pbnQoZ3JpZCwgaGVyZVgsIGhlcmVZLCBpbmNsdWRlVXAsIGluY2x1ZGVEb3duKToKICAgICAgICAgICAgICAgICAgICAgICAgaWYgZ3JpZFt4LHldLndhdGVyICE9IDAgYW5kICh4LHkpIG5vdCBpbiBleHBsb3JlZDoKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHRvRXhwbG9yZS5hcHBlbmQoKHgseSkpCiAgICAgICAgICAgICAgICAgICAgICAgICAgICB3YXRlclJlZ2lvbnNbaSxqXS5hcHBlbmQoKHgseSkpCiAgICAgICAgICAgICAgICAgICAgZm9yIHgsIHkgaW4gYWRqb2ludChncmlkLCBoZXJlWCwgaGVyZVksIGluY2x1ZGVVcCwgVHJ1ZSk6CiAgICAgICAgICAgICAgICAgICAgICAgIGVkZ2VzW2ksal1baGVyZVgsaGVyZVldW3gseV0gPSBNQVhfRkxPVwogICAgICAgICAgICAgICAgICAgICAgICBpZiBncmlkW3gseV0ud2F0ZXIgIT0gZ3JpZFt4LHldLmdldENhcGFjaXR5KCk6CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBvdXRsZXRzW2ksal0uYXBwZW5kKCh4LHkpKQogICAgcmV0dXJuIHdhdGVyUmVnaW9ucywgb3V0bGV0cywgZWRnZXMKCmRlZiBmaW5kSGVpZ2h0KGdyaWQsIHBvaW50KToKICAgIHJldHVybiAoaGVpZ2h0IC0gcG9pbnRbMF0pICogTUFYX0NBUEFDSVRZICsgZ3JpZFtwb2ludF0ud2F0ZXIKCmRlZiBmaW5kSGlnaGVzdFBvaW50KGdyaWQsIHJlZ2lvbik6CiAgICBoaWdoZXN0UG9pbnQgPSByZWdpb25bMF0KICAgIGhpZ2hlc3RIZWlnaHQgPSBmaW5kSGVpZ2h0KGdyaWQsIGhpZ2hlc3RQb2ludCkKICAgIGZvciBwb2ludCBpbiByZWdpb246CiAgICAgICAgaGVpZ2h0ID0gZmluZEhlaWdodChncmlkLCBwb2ludCkKICAgICAgICBpZiBoZWlnaHQgPiBoaWdoZXN0SGVpZ2h0OgogICAgICAgICAgICBoaWdoZXN0SGVpZ2h0ID0gaGVpZ2h0CiAgICAgICAgICAgIGhpZ2hlc3RQb2ludCA9IHBvaW50CiAgICByZXR1cm4gaGlnaGVzdFBvaW50CgpkZWYgZmluZExvd2VzdFBvaW50KGdyaWQsIHJlZ2lvbik6CiAgICBsb3dlc3RQb2ludCA9IHJlZ2lvblswXQogICAgbG93ZXN0SGVpZ2h0ID0gZmluZEhlaWdodChncmlkLCBsb3dlc3RQb2ludCkKICAgIGZvciBwb2ludCBpbiByZWdpb246CiAgICAgICAgaGVpZ2h0ID0gZmluZEhlaWdodChncmlkLCBwb2ludCkKICAgICAgICBpZiBoZWlnaHQgPCBsb3dlc3RIZWlnaHQ6CiAgICAgICAgICAgIGxvd2VzdEhlaWdodCA9IGhlaWdodAogICAgICAgICAgICBsb3dlc3RQb2ludCA9IHBvaW50CiAgICByZXR1cm4gbG93ZXN0UG9pbnQKCmRlZiBtb3ZlV2F0ZXIoZ3JpZCwgc3RhcnQsIGVuZCwgcmVnaW9uLCBlZGdlKToKICAgICIiIk1vdmUgYSB1bml0IG9mIHdhdGVyIGZyb20gc3RhcnQgdG8gZW5kLiBSZXR1cm4gVHJ1ZSBpZiBzdWNjZXNzZnVsLiIiIgogICAgcGF0aCA9IGFTdGFyUmVnaW9uKHN0YXJ0LCBlbmQsIHJlZ2lvbiwgZWRnZSkKICAgIGlmIGxlbihwYXRoKSA9PSAwOgogICAgICAgIHJldHVybiBGYWxzZQoKICAgIGdyaWRbc3RhcnRdLndhdGVyIC09IDEKICAgIHN0ZXBTdGFydCA9IHN0YXJ0CiAgICBmb3Igc3RlcEVuZCBpbiBwYXRoWzE6XToKICAgICAgICBlZGdlW3N0ZXBTdGFydF1bc3RlcEVuZF0gLT0gMQogICAgICAgIGlmIGVkZ2Vbc3RlcFN0YXJ0XVtzdGVwRW5kXSA9PSAwOgogICAgICAgICAgICBlZGdlW3N0ZXBTdGFydF0ucG9wKHN0ZXBFbmQpCiAgICAgICAgICAgIGlmIGxlbihlZGdlW3N0ZXBTdGFydF0pID09IDA6CiAgICAgICAgICAgICAgICBlZGdlLnBvcChzdGVwU3RhcnQpCiAgICAgICAgc3RlcFN0YXJ0ID0gc3RlcEVuZAogICAgZ3JpZFtlbmRdLndhdGVyICs9IDEKICAgIAogICAgcmV0dXJuIFRydWUKCmRlZiBkaXNwbGF5R3JpZChncmlkKToKICAgIHByaW50CiAgICBmb3IgaSBpbiByYW5nZShoZWlnaHQpOgogICAgICAgIHJvdyA9ICcnCiAgICAgICAgZm9yIGogaW4gcmFuZ2Uod2lkdGgpOgogICAgICAgICAgICBncmlkW2ksal0udXBkYXRlVHlwZShncmlkW2krMSxqXSkKICAgICAgICAgICAgcm93ICs9IHN0cihncmlkW2ksal0pCiAgICAgICAgcm93ICs9ICcgJwogICAgICAgIGZvciBqIGluIHJhbmdlKHdpZHRoKToKICAgICAgICAgICAgcm93ICs9ICgnJXgnJShncmlkW2ksal0ud2F0ZXIgLyAxMCkgaWYgZ3JpZFtpLGpdLndhdGVyIDwgMTYwIGVsc2UgJysnKQogICAgICAgIHByaW50IHJvdwoKZGVmIG1haW4oZ3JpZCk6CiAgICB0ID0gMAogICAgd2hpbGUgdCA8IDIwOgogICAgICAgIGRpc3BsYXlHcmlkKGdyaWQpCiAgICAgICAgbmV3R3JpZCA9IGRlZmF1bHRkaWN0KGxhbWJkYSA6IENlbGwoU1BBQ0UsIEZhbHNlKSkKICAgICAgICBmb3IgaSwgaiBpbiBwcm9kdWN0KHJhbmdlKGhlaWdodCksIHJhbmdlKHdpZHRoKSk6CiAgICAgICAgICAgIGNlbGwgPSBncmlkW2ksal0KICAgICAgICAgICAgbmV3Q2VsbCA9IG5ld0dyaWRbaSxqXQogICAgICAgICAgICBuZXdDZWxsLmNvcHlDZWxsKGNlbGwpCiAgICAgICAgICAgIGlmIGNlbGwuaXNTb3VyY2U6CiAgICAgICAgICAgICAgICBuZXdDZWxsLndhdGVyICs9IFNPVVJDRV9SQVRFCiAgICAgICAgZ3JpZCA9IG5ld0dyaWQKICAgICAgICAKICAgICAgICB3YXRlclJlZ2lvbnMsIG91dGxldHMsIGVkZ2VzID0gZmluZFdhdGVyUmVnaW9ucyhncmlkLCBoZWlnaHQsIHdpZHRoKQogICAgICAgIAogICAgICAgIG1vdmVkU29tZXRoaW5nID0gVHJ1ZQogICAgICAgIHdoaWxlIG1vdmVkU29tZXRoaW5nOgogICAgICAgICAgICBtb3ZlZFNvbWV0aGluZyA9IEZhbHNlCiAgICAgICAgICAgIGZvciByZWdpb25LZXkgaW4gd2F0ZXJSZWdpb25zLmtleXMoKToKICAgICAgICAgICAgICAgIHdhdGVyUmVnaW9uID0gd2F0ZXJSZWdpb25zW3JlZ2lvbktleV0KICAgICAgICAgICAgICAgIG91dGxldCA9IG91dGxldHNbcmVnaW9uS2V5XQogICAgICAgICAgICAgICAgZWRnZSA9IGVkZ2VzW3JlZ2lvbktleV0KICAgICAgICAgICAgICAgIHN0YXJ0ID0gZmluZEhpZ2hlc3RQb2ludChncmlkLCB3YXRlclJlZ2lvbikKICAgICAgICAgICAgICAgIGVuZCA9IGZpbmRMb3dlc3RQb2ludChncmlkLCBvdXRsZXQpCiAgICAgICAgICAgICAgICBpZiBmaW5kSGVpZ2h0KGdyaWQsIHN0YXJ0KSA+IGZpbmRIZWlnaHQoZ3JpZCwgZW5kKToKICAgICAgICAgICAgICAgICAgICBtb3ZlZFNvbWV0aGluZyA9IG1vdmVXYXRlcihncmlkLCBzdGFydCwgZW5kLCB3YXRlclJlZ2lvbiArIFtlbmRdLCBlZGdlKQogICAgICAgICAgICAgICAgICAgIGlmIGdyaWRbc3RhcnRdLndhdGVyID09IDA6CiAgICAgICAgICAgICAgICAgICAgICAgIHdhdGVyUmVnaW9uLnJlbW92ZShzdGFydCkKICAgICAgICAgICAgICAgICAgICAgICAgaWYgbGVuKHdhdGVyUmVnaW9uKSA9PSAwOgogICAgICAgICAgICAgICAgICAgICAgICAgICAgd2F0ZXJSZWdpb25zLnBvcChyZWdpb25LZXkpCgogICAgICAgIHQgKz0gMQoKaWYgX19uYW1lX18gPT0gJ19fbWFpbl9fJzoKICAgIGltcG9ydCBkb2N0ZXN0CiAgICAjIERvZXNuJ3QgdGVzdCBpbm5lciBmdW5jdGlvbnMhCiAgICBmYWlsdXJlcywgcGFzc2VzID0gZG9jdGVzdC50ZXN0bW9kKHJhaXNlX29uX2Vycm9yPUZhbHNlKQogICAgaWYgZmFpbHVyZXMgPT0gMDoKICAgICAgICBtYWluKGdyaWQpCiAgICBlbHNlOgogICAgICAgIHByaW50ICdTdG9wcGluZyB3aXRoICVkIGZhaWx1cmVzJyVmYWlsdXJlcw==