import math
import random
 
 
class Knot():
    """Knot object which contains its state space and Shannon entropy."""
 
    def __init__(self, state_space):
        self.space = state_space  # state_space = {state:weight}
        self.entropy = Knot.shannon(state_space)
 
    @staticmethod
    def shannon(state_space):
        """Returns the Shannon entropy of the `state_space`."""
        if isinstance(state_space, int) or len(state_space) == 1:
            return 0
        ws = sum(state_space.values())
        if ws == 0:
            print(state_space)
        return math.log(ws) - sum(map(lambda x: x * math.log(x), state_space.values())) / ws
 
    def __len__(self):
        return len(self.space)
 
    def __str__(self):
        return self.space
 
 
class CollapseError(StopIteration):
    pass
 
 
class WaveFunction():
    """Wave Function of the to-be-determined output
 
    Attributes：
        wave: A 2-D matrix which contains all the Knots.
        size: The shape of the wave.
 
        options:  All the optional functions.
        patterns: The index => pattern pairs.     
        weights:  Record the weight corresponding to the index of each pattern 
        rules:    Record patterns that each patterns can match in each directions.
 
    """
 
    def __init__(self,
                 size,
                 entry,
                 N=3,
                 *,
                 surveil=True,
                 AllRules=False,
                 Rotation=False,
                 Reflection=False,
                 PeriodicInput=False,
                 PeriodicOutput=False):
        # Scan the entry and extract patterns and rules.
        self.N = N
        self.options = {
            'PeriIpt': PeriodicInput,
            'PeriOpt': PeriodicOutput,
            'Rot': Rotation,
            'Ref': Reflection,
            'surv': surveil
        }
        self.patterns, self.weights, self.rules = {}, [], []
        self.BuildPatterns(entry)
        self.patterns = {index: pattern for pattern, index in self.patterns.items()}
        if N > 1 and AllRules:
            self.make_all_rules()
 
 
        self.size = (size[0] - N + 1, size[1] - N + 1)
        self.Stack = []
 
        # Initializes the 2-D WaveFunction matrix, each Knot of the matrix
        # starts with all states as possible. No state is forbidden yet.
        # And every Knot is waited to collapse.
        state_space = {state: self.weights[state] for state in self.patterns.keys()}
        self.wave = [[Knot(state_space.copy()) for i in range(self.size[1])] for j in range(self.size[0])]
        self.wait_to_collapse = set((x, y) for x in range(self.size[0]) for y in range(self.size[1]))
 
    @staticmethod
    def symmetry(m, reflect, rotate):
        """Returns matrix which performed symmetry operations."""
 
        def LR_reflect(m):
            return tuple(reversed(m))
 
        def UD_reflect(m):
            return tuple(tuple(reversed(m[x][:])) for x in range(len(m)))
 
        operand = {m}
        if reflect:
            operand = operand | {LR_reflect(m), UD_reflect(m), LR_reflect(UD_reflect(m))}
        if rotate:
            m1 = tuple(tuple(m[y][x] for y in range(len(m[0]))) for x in range(len(m)))
            operand = operand | {LR_reflect(m1), UD_reflect(m1), LR_reflect(UD_reflect(m1))}
 
        return operand
 
    def BuildPatterns(self, entry):
        """Parses the `entry` matrix. Extracts patterns, weights and adjacent rules. """
        N = self.N
        for ent in WaveFunction.symmetry(entry, self.options['Ref'], self.options['Rot']):
            index = len(self.patterns)
 
            if self.options['PeriIpt']:
                width, height = len(ent) - 1, len(ent[0]) - 1
                ent = [ent[x][:] + ent[x][:N - 1] for x in range(len(ent))]
                ent = ent[:] + ent[:N - 1]
            else:
                width, height = len(ent) - N + 1, len(ent[0]) - N + 1
 
            matrix = [[None] * height for _ in range(width)]
            for x in range(width):
                for y in range(height):
                    # Extract an N*N matrix as a pattern with the upper left corner being (x, y).
                    pat = tuple(tuple(ent[x1][y:y + N]) for x1 in range(x, x + N))
 
                    # If this pattern already exists, simply increment its weight. Otherwise, records
                    # the new pattern and initializes its weight as 1, then increment the pattern index.
                    try:
                        matrix[x][y] = self.patterns[pat]
                        self.weights[matrix[x][y]] += 1
                    except KeyError:
                        self.patterns[pat] = matrix[x][y] = index
                        self.weights.append(1)
                        self.rules.append([set() for _ in range(4)])
                        index += 1
                    self.make_rule((x, y), matrix)
 
    def make_rule(self, position, matrix):
        """Makes the adjacent-rule for the pattern at the location with 
        patterns at its left side and its top side."""
        # The order of directions: (-1,0), (1,0), (0,-1), (0,1)
        (x, y) = position
        if x > 0:
            self.rules[matrix[x][y]][0].add(matrix[x - 1][y])
            self.rules[matrix[x - 1][y]][1].add(matrix[x][y])
        if y > 0:
            self.rules[matrix[x][y]][2].add(matrix[x][y - 1])
            self.rules[matrix[x][y - 1]][3].add(matrix[x][y])
 
    def make_all_rules(self):
        """Traverses patterns to match all the possible rules.
        This method may allow some adjacent rules that do not exist in the original input."""
 
        def compatible(pattern1, pattern2, direction):
            """Returns `True` if `pattern2` is compatible with `pattern1` in the `direction`,
            otherwise return `False`."""
            if direction == 0:
                return pattern1[:-1] == pattern2[1:]
            if direction == 2:
                return [line[:-1] for line in pattern1] == [line[1:] for line in pattern2]
 
        for index in range(len(self.patterns)):
            for ind in range(index + 1):
                for direction in (0, 2):
                    if compatible(self.patterns[index], self.patterns[ind], direction):
                        self.rules[index][direction].add(ind)
                        self.rules[ind][direction + 1].add(index)
 
    def __getitem__(self, index):
        return self.wave[index[0]][index[1]]
 
    def __setitem__(self, index, value):
        self.wave[index[0]][index[1]] = value
 
    def min_entropy_pos(self):
        """Returns the position of the Knot whose statespace has the lowest entropy."""
        min_entropy = float("inf")
        for Knot in self.wait_to_collapse:
            noise = random.random() / 1000
            # Add some noise to mix things up a little
            if self[Knot].entropy - noise < min_entropy:
                position = Knot[:]
                min_entropy = self[position].entropy - noise
        return position
 
    def neighbor(self, position):
        """Yields neighboring Knots and their directions of a given `position`."""
        if self.options['PeriOpt']:
            if position[0] == 0:
                yield (self.size[0] - 1, position[1]), 0
            elif position[0] == self.size[0] - 1:
                yield (0, position[1]), 1
            if position[1] == 0:
                yield (position[0], self.size[1] - 1), 2
            elif position[1] == self.size[1] - 1:
                yield (position[0], 0), 3
 
        if position[0] > 0:
            yield (position[0] - 1, position[1]), 0
        if position[0] < self.size[0] - 1:
            yield (position[0] + 1, position[1]), 1
        if position[1] > 0:
            yield (position[0], position[1] - 1), 2
        if position[1] < self.size[1] - 1:
            yield (position[0], position[1] + 1), 3
 
    def collapse(self, position):
        """Collapses the Knot at `position`, and then propagates the consequences. """
        (x, y) = position
        if len(self[position]) < 1:
            return self.backtrack()
        else:
            if len(self[position]) > 1:
                # Choose one possible pattern randomly and push this changed Knot into the Stack.
                states, w = list(self[position].space.keys()), list(self[position].space.values())
                elem = random.choices(states, weights=w)[0]
                del self.wave[x][y].space[elem]
                self.Stack.append({position: self[position].space.copy()})
                self[x, y] = Knot({elem: 1})
            self.wait_to_collapse.remove(position)
            return self.propagate(position)
 
    def propagate(self, position):
        """Propagates the consequences of the wavefunction collapse or statespace 
        changing at `position`.This method keeps propagating the consequences of 
        the consequences,and so on until no consequences remain. 
        """
        PropagStack = [position]
        changed = {position}
 
        while PropagStack:
            pos = PropagStack.pop()
 
            for nb, direction in self.neighbor(pos):
                if nb in self.wait_to_collapse:
                    available = set.union(*[self.rules[state][direction] for state in self[pos].space.keys()])
                    if not set(self[nb].space.keys()).issubset(available):
                        available = available & set(self[nb].space.keys())
                        if len(available) == 0:
                            return self.backtrack()
 
                        elif self.Stack and (nb not in self.Stack[-1].keys()):
                            # Push this changed Knot into the Stack.
                            self.Stack[-1][nb] = self[nb].space.copy()
                        self[nb] = Knot({state: self.weights[state] for state in available})
                        PropagStack.append(nb)
                        changed.add(nb)
        return changed
 
    def backtrack(self):
        """Backtracks to the previous step. 
        If there is no way to backtrack then this method raises CollapseError. """
        print('0')
        if len(self.Stack):
            step = self.Stack.pop()
            # Restore all the Knot affected by the last collapse.
            for (position, space) in step.items():
                self[position] = Knot(space)
                self.wait_to_collapse.add(position)
            return set(step.keys())
        else:
            raise CollapseError("No Sulotion")
 
    def observe(self, surveil):
        '''Observe the whole WaveFunction'''
        try:
            if surveil:
                while self.wait_to_collapse:
                    yield self.collapse(self.min_entropy_pos())
            else:
                while self.wait_to_collapse:
                    list(self.collapse(self.min_entropy_pos()))
                yield [(x, y) for x in range(self.size[0]) for y in range(self.size[1])]
        except CollapseError:
            raise CollapseError
 
if __name__ == "__main__":
    def MatrixProcessor(entry, size, N, options):
        def update(matrix, position, w, N):
            limit_i = N if position[0] == w.size[0] - 1 else 1
            limit_j = N if position[1] == w.size[1] - 1 else 1
            for i in range(limit_i):
                for j in range(limit_j):
                    matrix[position[0] + i][position[1] + j] = w.patterns[list(w[position].space.keys())[0]][i][j]
            return matrix
 
        w = WaveFunction(size, entry, N=N, **options)
        matrix = [[None] * size[0] for _ in range(size[1])]
 
        for changed in w.observe(w.options['surv']):
            for pos in changed:
                matrix = update(matrix, pos, w, N)
        for eachline in matrix:
            print(eachline)
 
    # This is a demo to show a how wfc is working on string matrix.
    # Imagine that below is a map, where 'L' = land, 'C' = coast, 'S' = sea,
    # and now we will show you that how wfc generate maps with some natural rules, such as land cannot be next to sea.
    entry = (
        ('L', 'L', 'L', 'L', 'L', 'L', 'L'),
        ('L', 'L', 'C', 'L', 'L', 'L', 'L'),
        ('C', 'C', 'S', 'C', 'C', 'L', 'L'),
        ('S', 'S', 'S', 'S', 'S', 'C', 'L'),
        ('S', 'S', ':3', 'S', 'S', 'S', 'C')
    )
    options = {        
        'AllRules':0,
        'surveil':0,
        'PeriodicInput':0,
        'PeriodicOutput':0,
        'Rotation':0,
        'Reflection':0
    }
    MatrixProcessor(entry, (10,10),N=1,options=options)

aW1wb3J0IG1hdGgKaW1wb3J0IHJhbmRvbQoKCmNsYXNzIEtub3QoKToKICAgICIiIktub3Qgb2JqZWN0IHdoaWNoIGNvbnRhaW5zIGl0cyBzdGF0ZSBzcGFjZSBhbmQgU2hhbm5vbiBlbnRyb3B5LiIiIgoKICAgIGRlZiBfX2luaXRfXyhzZWxmLCBzdGF0ZV9zcGFjZSk6CiAgICAgICAgc2VsZi5zcGFjZSA9IHN0YXRlX3NwYWNlICAjIHN0YXRlX3NwYWNlID0ge3N0YXRlOndlaWdodH0KICAgICAgICBzZWxmLmVudHJvcHkgPSBLbm90LnNoYW5ub24oc3RhdGVfc3BhY2UpCgogICAgQHN0YXRpY21ldGhvZAogICAgZGVmIHNoYW5ub24oc3RhdGVfc3BhY2UpOgogICAgICAgICIiIlJldHVybnMgdGhlIFNoYW5ub24gZW50cm9weSBvZiB0aGUgYHN0YXRlX3NwYWNlYC4iIiIKICAgICAgICBpZiBpc2luc3RhbmNlKHN0YXRlX3NwYWNlLCBpbnQpIG9yIGxlbihzdGF0ZV9zcGFjZSkgPT0gMToKICAgICAgICAgICAgcmV0dXJuIDAKICAgICAgICB3cyA9IHN1bShzdGF0ZV9zcGFjZS52YWx1ZXMoKSkKICAgICAgICBpZiB3cyA9PSAwOgogICAgICAgICAgICBwcmludChzdGF0ZV9zcGFjZSkKICAgICAgICByZXR1cm4gbWF0aC5sb2cod3MpIC0gc3VtKG1hcChsYW1iZGEgeDogeCAqIG1hdGgubG9nKHgpLCBzdGF0ZV9zcGFjZS52YWx1ZXMoKSkpIC8gd3MKCiAgICBkZWYgX19sZW5fXyhzZWxmKToKICAgICAgICByZXR1cm4gbGVuKHNlbGYuc3BhY2UpCgogICAgZGVmIF9fc3RyX18oc2VsZik6CiAgICAgICAgcmV0dXJuIHNlbGYuc3BhY2UKCgpjbGFzcyBDb2xsYXBzZUVycm9yKFN0b3BJdGVyYXRpb24pOgogICAgcGFzcwoKCmNsYXNzIFdhdmVGdW5jdGlvbigpOgogICAgIiIiV2F2ZSBGdW5jdGlvbiBvZiB0aGUgdG8tYmUtZGV0ZXJtaW5lZCBvdXRwdXQKICAgIAogICAgQXR0cmlidXRlc++8mgogICAgICAgIHdhdmU6IEEgMi1EIG1hdHJpeCB3aGljaCBjb250YWlucyBhbGwgdGhlIEtub3RzLgogICAgICAgIHNpemU6IFRoZSBzaGFwZSBvZiB0aGUgd2F2ZS4KCiAgICAgICAgb3B0aW9uczogIEFsbCB0aGUgb3B0aW9uYWwgZnVuY3Rpb25zLgogICAgICAgIHBhdHRlcm5zOiBUaGUgaW5kZXggPT4gcGF0dGVybiBwYWlycy4gICAgIAogICAgICAgIHdlaWdodHM6ICBSZWNvcmQgdGhlIHdlaWdodCBjb3JyZXNwb25kaW5nIHRvIHRoZSBpbmRleCBvZiBlYWNoIHBhdHRlcm4gCiAgICAgICAgcnVsZXM6ICAgIFJlY29yZCBwYXR0ZXJucyB0aGF0IGVhY2ggcGF0dGVybnMgY2FuIG1hdGNoIGluIGVhY2ggZGlyZWN0aW9ucy4KICAgICAKICAgICIiIgoKICAgIGRlZiBfX2luaXRfXyhzZWxmLAogICAgICAgICAgICAgICAgIHNpemUsCiAgICAgICAgICAgICAgICAgZW50cnksCiAgICAgICAgICAgICAgICAgTj0zLAogICAgICAgICAgICAgICAgICosCiAgICAgICAgICAgICAgICAgc3VydmVpbD1UcnVlLAogICAgICAgICAgICAgICAgIEFsbFJ1bGVzPUZhbHNlLAogICAgICAgICAgICAgICAgIFJvdGF0aW9uPUZhbHNlLAogICAgICAgICAgICAgICAgIFJlZmxlY3Rpb249RmFsc2UsCiAgICAgICAgICAgICAgICAgUGVyaW9kaWNJbnB1dD1GYWxzZSwKICAgICAgICAgICAgICAgICBQZXJpb2RpY091dHB1dD1GYWxzZSk6CiAgICAgICAgIyBTY2FuIHRoZSBlbnRyeSBhbmQgZXh0cmFjdCBwYXR0ZXJucyBhbmQgcnVsZXMuCiAgICAgICAgc2VsZi5OID0gTgogICAgICAgIHNlbGYub3B0aW9ucyA9IHsKICAgICAgICAgICAgJ1BlcmlJcHQnOiBQZXJpb2RpY0lucHV0LAogICAgICAgICAgICAnUGVyaU9wdCc6IFBlcmlvZGljT3V0cHV0LAogICAgICAgICAgICAnUm90JzogUm90YXRpb24sCiAgICAgICAgICAgICdSZWYnOiBSZWZsZWN0aW9uLAogICAgICAgICAgICAnc3Vydic6IHN1cnZlaWwKICAgICAgICB9CiAgICAgICAgc2VsZi5wYXR0ZXJucywgc2VsZi53ZWlnaHRzLCBzZWxmLnJ1bGVzID0ge30sIFtdLCBbXQogICAgICAgIHNlbGYuQnVpbGRQYXR0ZXJucyhlbnRyeSkKICAgICAgICBzZWxmLnBhdHRlcm5zID0ge2luZGV4OiBwYXR0ZXJuIGZvciBwYXR0ZXJuLCBpbmRleCBpbiBzZWxmLnBhdHRlcm5zLml0ZW1zKCl9CiAgICAgICAgaWYgTiA+IDEgYW5kIEFsbFJ1bGVzOgogICAgICAgICAgICBzZWxmLm1ha2VfYWxsX3J1bGVzKCkKCgogICAgICAgIHNlbGYuc2l6ZSA9IChzaXplWzBdIC0gTiArIDEsIHNpemVbMV0gLSBOICsgMSkKICAgICAgICBzZWxmLlN0YWNrID0gW10KCiAgICAgICAgIyBJbml0aWFsaXplcyB0aGUgMi1EIFdhdmVGdW5jdGlvbiBtYXRyaXgsIGVhY2ggS25vdCBvZiB0aGUgbWF0cml4CiAgICAgICAgIyBzdGFydHMgd2l0aCBhbGwgc3RhdGVzIGFzIHBvc3NpYmxlLiBObyBzdGF0ZSBpcyBmb3JiaWRkZW4geWV0LgogICAgICAgICMgQW5kIGV2ZXJ5IEtub3QgaXMgd2FpdGVkIHRvIGNvbGxhcHNlLgogICAgICAgIHN0YXRlX3NwYWNlID0ge3N0YXRlOiBzZWxmLndlaWdodHNbc3RhdGVdIGZvciBzdGF0ZSBpbiBzZWxmLnBhdHRlcm5zLmtleXMoKX0KICAgICAgICBzZWxmLndhdmUgPSBbW0tub3Qoc3RhdGVfc3BhY2UuY29weSgpKSBmb3IgaSBpbiByYW5nZShzZWxmLnNpemVbMV0pXSBmb3IgaiBpbiByYW5nZShzZWxmLnNpemVbMF0pXQogICAgICAgIHNlbGYud2FpdF90b19jb2xsYXBzZSA9IHNldCgoeCwgeSkgZm9yIHggaW4gcmFuZ2Uoc2VsZi5zaXplWzBdKSBmb3IgeSBpbiByYW5nZShzZWxmLnNpemVbMV0pKQoKICAgIEBzdGF0aWNtZXRob2QKICAgIGRlZiBzeW1tZXRyeShtLCByZWZsZWN0LCByb3RhdGUpOgogICAgICAgICIiIlJldHVybnMgbWF0cml4IHdoaWNoIHBlcmZvcm1lZCBzeW1tZXRyeSBvcGVyYXRpb25zLiIiIgoKICAgICAgICBkZWYgTFJfcmVmbGVjdChtKToKICAgICAgICAgICAgcmV0dXJuIHR1cGxlKHJldmVyc2VkKG0pKQoKICAgICAgICBkZWYgVURfcmVmbGVjdChtKToKICAgICAgICAgICAgcmV0dXJuIHR1cGxlKHR1cGxlKHJldmVyc2VkKG1beF1bOl0pKSBmb3IgeCBpbiByYW5nZShsZW4obSkpKQoKICAgICAgICBvcGVyYW5kID0ge219CiAgICAgICAgaWYgcmVmbGVjdDoKICAgICAgICAgICAgb3BlcmFuZCA9IG9wZXJhbmQgfCB7TFJfcmVmbGVjdChtKSwgVURfcmVmbGVjdChtKSwgTFJfcmVmbGVjdChVRF9yZWZsZWN0KG0pKX0KICAgICAgICBpZiByb3RhdGU6CiAgICAgICAgICAgIG0xID0gdHVwbGUodHVwbGUobVt5XVt4XSBmb3IgeSBpbiByYW5nZShsZW4obVswXSkpKSBmb3IgeCBpbiByYW5nZShsZW4obSkpKQogICAgICAgICAgICBvcGVyYW5kID0gb3BlcmFuZCB8IHtMUl9yZWZsZWN0KG0xKSwgVURfcmVmbGVjdChtMSksIExSX3JlZmxlY3QoVURfcmVmbGVjdChtMSkpfQoKICAgICAgICByZXR1cm4gb3BlcmFuZAoKICAgIGRlZiBCdWlsZFBhdHRlcm5zKHNlbGYsIGVudHJ5KToKICAgICAgICAiIiJQYXJzZXMgdGhlIGBlbnRyeWAgbWF0cml4LiBFeHRyYWN0cyBwYXR0ZXJucywgd2VpZ2h0cyBhbmQgYWRqYWNlbnQgcnVsZXMuICIiIgogICAgICAgIE4gPSBzZWxmLk4KICAgICAgICBmb3IgZW50IGluIFdhdmVGdW5jdGlvbi5zeW1tZXRyeShlbnRyeSwgc2VsZi5vcHRpb25zWydSZWYnXSwgc2VsZi5vcHRpb25zWydSb3QnXSk6CiAgICAgICAgICAgIGluZGV4ID0gbGVuKHNlbGYucGF0dGVybnMpCgogICAgICAgICAgICBpZiBzZWxmLm9wdGlvbnNbJ1BlcmlJcHQnXToKICAgICAgICAgICAgICAgIHdpZHRoLCBoZWlnaHQgPSBsZW4oZW50KSAtIDEsIGxlbihlbnRbMF0pIC0gMQogICAgICAgICAgICAgICAgZW50ID0gW2VudFt4XVs6XSArIGVudFt4XVs6TiAtIDFdIGZvciB4IGluIHJhbmdlKGxlbihlbnQpKV0KICAgICAgICAgICAgICAgIGVudCA9IGVudFs6XSArIGVudFs6TiAtIDFdCiAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICB3aWR0aCwgaGVpZ2h0ID0gbGVuKGVudCkgLSBOICsgMSwgbGVuKGVudFswXSkgLSBOICsgMQoKICAgICAgICAgICAgbWF0cml4ID0gW1tOb25lXSAqIGhlaWdodCBmb3IgXyBpbiByYW5nZSh3aWR0aCldCiAgICAgICAgICAgIGZvciB4IGluIHJhbmdlKHdpZHRoKToKICAgICAgICAgICAgICAgIGZvciB5IGluIHJhbmdlKGhlaWdodCk6CiAgICAgICAgICAgICAgICAgICAgIyBFeHRyYWN0IGFuIE4qTiBtYXRyaXggYXMgYSBwYXR0ZXJuIHdpdGggdGhlIHVwcGVyIGxlZnQgY29ybmVyIGJlaW5nICh4LCB5KS4KICAgICAgICAgICAgICAgICAgICBwYXQgPSB0dXBsZSh0dXBsZShlbnRbeDFdW3k6eSArIE5dKSBmb3IgeDEgaW4gcmFuZ2UoeCwgeCArIE4pKQoKICAgICAgICAgICAgICAgICAgICAjIElmIHRoaXMgcGF0dGVybiBhbHJlYWR5IGV4aXN0cywgc2ltcGx5IGluY3JlbWVudCBpdHMgd2VpZ2h0LiBPdGhlcndpc2UsIHJlY29yZHMKICAgICAgICAgICAgICAgICAgICAjIHRoZSBuZXcgcGF0dGVybiBhbmQgaW5pdGlhbGl6ZXMgaXRzIHdlaWdodCBhcyAxLCB0aGVuIGluY3JlbWVudCB0aGUgcGF0dGVybiBpbmRleC4KICAgICAgICAgICAgICAgICAgICB0cnk6CiAgICAgICAgICAgICAgICAgICAgICAgIG1hdHJpeFt4XVt5XSA9IHNlbGYucGF0dGVybnNbcGF0XQogICAgICAgICAgICAgICAgICAgICAgICBzZWxmLndlaWdodHNbbWF0cml4W3hdW3ldXSArPSAxCiAgICAgICAgICAgICAgICAgICAgZXhjZXB0IEtleUVycm9yOgogICAgICAgICAgICAgICAgICAgICAgICBzZWxmLnBhdHRlcm5zW3BhdF0gPSBtYXRyaXhbeF1beV0gPSBpbmRleAogICAgICAgICAgICAgICAgICAgICAgICBzZWxmLndlaWdodHMuYXBwZW5kKDEpCiAgICAgICAgICAgICAgICAgICAgICAgIHNlbGYucnVsZXMuYXBwZW5kKFtzZXQoKSBmb3IgXyBpbiByYW5nZSg0KV0pCiAgICAgICAgICAgICAgICAgICAgICAgIGluZGV4ICs9IDEKICAgICAgICAgICAgICAgICAgICBzZWxmLm1ha2VfcnVsZSgoeCwgeSksIG1hdHJpeCkKCiAgICBkZWYgbWFrZV9ydWxlKHNlbGYsIHBvc2l0aW9uLCBtYXRyaXgpOgogICAgICAgICIiIk1ha2VzIHRoZSBhZGphY2VudC1ydWxlIGZvciB0aGUgcGF0dGVybiBhdCB0aGUgbG9jYXRpb24gd2l0aCAKICAgICAgICBwYXR0ZXJucyBhdCBpdHMgbGVmdCBzaWRlIGFuZCBpdHMgdG9wIHNpZGUuIiIiCiAgICAgICAgIyBUaGUgb3JkZXIgb2YgZGlyZWN0aW9uczogKC0xLDApLCAoMSwwKSwgKDAsLTEpLCAoMCwxKQogICAgICAgICh4LCB5KSA9IHBvc2l0aW9uCiAgICAgICAgaWYgeCA+IDA6CiAgICAgICAgICAgIHNlbGYucnVsZXNbbWF0cml4W3hdW3ldXVswXS5hZGQobWF0cml4W3ggLSAxXVt5XSkKICAgICAgICAgICAgc2VsZi5ydWxlc1ttYXRyaXhbeCAtIDFdW3ldXVsxXS5hZGQobWF0cml4W3hdW3ldKQogICAgICAgIGlmIHkgPiAwOgogICAgICAgICAgICBzZWxmLnJ1bGVzW21hdHJpeFt4XVt5XV1bMl0uYWRkKG1hdHJpeFt4XVt5IC0gMV0pCiAgICAgICAgICAgIHNlbGYucnVsZXNbbWF0cml4W3hdW3kgLSAxXV1bM10uYWRkKG1hdHJpeFt4XVt5XSkKCiAgICBkZWYgbWFrZV9hbGxfcnVsZXMoc2VsZik6CiAgICAgICAgIiIiVHJhdmVyc2VzIHBhdHRlcm5zIHRvIG1hdGNoIGFsbCB0aGUgcG9zc2libGUgcnVsZXMuCiAgICAgICAgVGhpcyBtZXRob2QgbWF5IGFsbG93IHNvbWUgYWRqYWNlbnQgcnVsZXMgdGhhdCBkbyBub3QgZXhpc3QgaW4gdGhlIG9yaWdpbmFsIGlucHV0LiIiIgoKICAgICAgICBkZWYgY29tcGF0aWJsZShwYXR0ZXJuMSwgcGF0dGVybjIsIGRpcmVjdGlvbik6CiAgICAgICAgICAgICIiIlJldHVybnMgYFRydWVgIGlmIGBwYXR0ZXJuMmAgaXMgY29tcGF0aWJsZSB3aXRoIGBwYXR0ZXJuMWAgaW4gdGhlIGBkaXJlY3Rpb25gLAogICAgICAgICAgICBvdGhlcndpc2UgcmV0dXJuIGBGYWxzZWAuIiIiCiAgICAgICAgICAgIGlmIGRpcmVjdGlvbiA9PSAwOgogICAgICAgICAgICAgICAgcmV0dXJuIHBhdHRlcm4xWzotMV0gPT0gcGF0dGVybjJbMTpdCiAgICAgICAgICAgIGlmIGRpcmVjdGlvbiA9PSAyOgogICAgICAgICAgICAgICAgcmV0dXJuIFtsaW5lWzotMV0gZm9yIGxpbmUgaW4gcGF0dGVybjFdID09IFtsaW5lWzE6XSBmb3IgbGluZSBpbiBwYXR0ZXJuMl0KCiAgICAgICAgZm9yIGluZGV4IGluIHJhbmdlKGxlbihzZWxmLnBhdHRlcm5zKSk6CiAgICAgICAgICAgIGZvciBpbmQgaW4gcmFuZ2UoaW5kZXggKyAxKToKICAgICAgICAgICAgICAgIGZvciBkaXJlY3Rpb24gaW4gKDAsIDIpOgogICAgICAgICAgICAgICAgICAgIGlmIGNvbXBhdGlibGUoc2VsZi5wYXR0ZXJuc1tpbmRleF0sIHNlbGYucGF0dGVybnNbaW5kXSwgZGlyZWN0aW9uKToKICAgICAgICAgICAgICAgICAgICAgICAgc2VsZi5ydWxlc1tpbmRleF1bZGlyZWN0aW9uXS5hZGQoaW5kKQogICAgICAgICAgICAgICAgICAgICAgICBzZWxmLnJ1bGVzW2luZF1bZGlyZWN0aW9uICsgMV0uYWRkKGluZGV4KQoKICAgIGRlZiBfX2dldGl0ZW1fXyhzZWxmLCBpbmRleCk6CiAgICAgICAgcmV0dXJuIHNlbGYud2F2ZVtpbmRleFswXV1baW5kZXhbMV1dCgogICAgZGVmIF9fc2V0aXRlbV9fKHNlbGYsIGluZGV4LCB2YWx1ZSk6CiAgICAgICAgc2VsZi53YXZlW2luZGV4WzBdXVtpbmRleFsxXV0gPSB2YWx1ZQoKICAgIGRlZiBtaW5fZW50cm9weV9wb3Moc2VsZik6CiAgICAgICAgIiIiUmV0dXJucyB0aGUgcG9zaXRpb24gb2YgdGhlIEtub3Qgd2hvc2Ugc3RhdGVzcGFjZSBoYXMgdGhlIGxvd2VzdCBlbnRyb3B5LiIiIgogICAgICAgIG1pbl9lbnRyb3B5ID0gZmxvYXQoImluZiIpCiAgICAgICAgZm9yIEtub3QgaW4gc2VsZi53YWl0X3RvX2NvbGxhcHNlOgogICAgICAgICAgICBub2lzZSA9IHJhbmRvbS5yYW5kb20oKSAvIDEwMDAKICAgICAgICAgICAgIyBBZGQgc29tZSBub2lzZSB0byBtaXggdGhpbmdzIHVwIGEgbGl0dGxlCiAgICAgICAgICAgIGlmIHNlbGZbS25vdF0uZW50cm9weSAtIG5vaXNlIDwgbWluX2VudHJvcHk6CiAgICAgICAgICAgICAgICBwb3NpdGlvbiA9IEtub3RbOl0KICAgICAgICAgICAgICAgIG1pbl9lbnRyb3B5ID0gc2VsZltwb3NpdGlvbl0uZW50cm9weSAtIG5vaXNlCiAgICAgICAgcmV0dXJuIHBvc2l0aW9uCgogICAgZGVmIG5laWdoYm9yKHNlbGYsIHBvc2l0aW9uKToKICAgICAgICAiIiJZaWVsZHMgbmVpZ2hib3JpbmcgS25vdHMgYW5kIHRoZWlyIGRpcmVjdGlvbnMgb2YgYSBnaXZlbiBgcG9zaXRpb25gLiIiIgogICAgICAgIGlmIHNlbGYub3B0aW9uc1snUGVyaU9wdCddOgogICAgICAgICAgICBpZiBwb3NpdGlvblswXSA9PSAwOgogICAgICAgICAgICAgICAgeWllbGQgKHNlbGYuc2l6ZVswXSAtIDEsIHBvc2l0aW9uWzFdKSwgMAogICAgICAgICAgICBlbGlmIHBvc2l0aW9uWzBdID09IHNlbGYuc2l6ZVswXSAtIDE6CiAgICAgICAgICAgICAgICB5aWVsZCAoMCwgcG9zaXRpb25bMV0pLCAxCiAgICAgICAgICAgIGlmIHBvc2l0aW9uWzFdID09IDA6CiAgICAgICAgICAgICAgICB5aWVsZCAocG9zaXRpb25bMF0sIHNlbGYuc2l6ZVsxXSAtIDEpLCAyCiAgICAgICAgICAgIGVsaWYgcG9zaXRpb25bMV0gPT0gc2VsZi5zaXplWzFdIC0gMToKICAgICAgICAgICAgICAgIHlpZWxkIChwb3NpdGlvblswXSwgMCksIDMKCiAgICAgICAgaWYgcG9zaXRpb25bMF0gPiAwOgogICAgICAgICAgICB5aWVsZCAocG9zaXRpb25bMF0gLSAxLCBwb3NpdGlvblsxXSksIDAKICAgICAgICBpZiBwb3NpdGlvblswXSA8IHNlbGYuc2l6ZVswXSAtIDE6CiAgICAgICAgICAgIHlpZWxkIChwb3NpdGlvblswXSArIDEsIHBvc2l0aW9uWzFdKSwgMQogICAgICAgIGlmIHBvc2l0aW9uWzFdID4gMDoKICAgICAgICAgICAgeWllbGQgKHBvc2l0aW9uWzBdLCBwb3NpdGlvblsxXSAtIDEpLCAyCiAgICAgICAgaWYgcG9zaXRpb25bMV0gPCBzZWxmLnNpemVbMV0gLSAxOgogICAgICAgICAgICB5aWVsZCAocG9zaXRpb25bMF0sIHBvc2l0aW9uWzFdICsgMSksIDMKCiAgICBkZWYgY29sbGFwc2Uoc2VsZiwgcG9zaXRpb24pOgogICAgICAgICIiIkNvbGxhcHNlcyB0aGUgS25vdCBhdCBgcG9zaXRpb25gLCBhbmQgdGhlbiBwcm9wYWdhdGVzIHRoZSBjb25zZXF1ZW5jZXMuICIiIgogICAgICAgICh4LCB5KSA9IHBvc2l0aW9uCiAgICAgICAgaWYgbGVuKHNlbGZbcG9zaXRpb25dKSA8IDE6CiAgICAgICAgICAgIHJldHVybiBzZWxmLmJhY2t0cmFjaygpCiAgICAgICAgZWxzZToKICAgICAgICAgICAgaWYgbGVuKHNlbGZbcG9zaXRpb25dKSA+IDE6CiAgICAgICAgICAgICAgICAjIENob29zZSBvbmUgcG9zc2libGUgcGF0dGVybiByYW5kb21seSBhbmQgcHVzaCB0aGlzIGNoYW5nZWQgS25vdCBpbnRvIHRoZSBTdGFjay4KICAgICAgICAgICAgICAgIHN0YXRlcywgdyA9IGxpc3Qoc2VsZltwb3NpdGlvbl0uc3BhY2Uua2V5cygpKSwgbGlzdChzZWxmW3Bvc2l0aW9uXS5zcGFjZS52YWx1ZXMoKSkKICAgICAgICAgICAgICAgIGVsZW0gPSByYW5kb20uY2hvaWNlcyhzdGF0ZXMsIHdlaWdodHM9dylbMF0KICAgICAgICAgICAgICAgIGRlbCBzZWxmLndhdmVbeF1beV0uc3BhY2VbZWxlbV0KICAgICAgICAgICAgICAgIHNlbGYuU3RhY2suYXBwZW5kKHtwb3NpdGlvbjogc2VsZltwb3NpdGlvbl0uc3BhY2UuY29weSgpfSkKICAgICAgICAgICAgICAgIHNlbGZbeCwgeV0gPSBLbm90KHtlbGVtOiAxfSkKICAgICAgICAgICAgc2VsZi53YWl0X3RvX2NvbGxhcHNlLnJlbW92ZShwb3NpdGlvbikKICAgICAgICAgICAgcmV0dXJuIHNlbGYucHJvcGFnYXRlKHBvc2l0aW9uKQoKICAgIGRlZiBwcm9wYWdhdGUoc2VsZiwgcG9zaXRpb24pOgogICAgICAgICIiIlByb3BhZ2F0ZXMgdGhlIGNvbnNlcXVlbmNlcyBvZiB0aGUgd2F2ZWZ1bmN0aW9uIGNvbGxhcHNlIG9yIHN0YXRlc3BhY2UgCiAgICAgICAgY2hhbmdpbmcgYXQgYHBvc2l0aW9uYC5UaGlzIG1ldGhvZCBrZWVwcyBwcm9wYWdhdGluZyB0aGUgY29uc2VxdWVuY2VzIG9mIAogICAgICAgIHRoZSBjb25zZXF1ZW5jZXMsYW5kIHNvIG9uIHVudGlsIG5vIGNvbnNlcXVlbmNlcyByZW1haW4uIAogICAgICAgICIiIgogICAgICAgIFByb3BhZ1N0YWNrID0gW3Bvc2l0aW9uXQogICAgICAgIGNoYW5nZWQgPSB7cG9zaXRpb259CgogICAgICAgIHdoaWxlIFByb3BhZ1N0YWNrOgogICAgICAgICAgICBwb3MgPSBQcm9wYWdTdGFjay5wb3AoKQoKICAgICAgICAgICAgZm9yIG5iLCBkaXJlY3Rpb24gaW4gc2VsZi5uZWlnaGJvcihwb3MpOgogICAgICAgICAgICAgICAgaWYgbmIgaW4gc2VsZi53YWl0X3RvX2NvbGxhcHNlOgogICAgICAgICAgICAgICAgICAgIGF2YWlsYWJsZSA9IHNldC51bmlvbigqW3NlbGYucnVsZXNbc3RhdGVdW2RpcmVjdGlvbl0gZm9yIHN0YXRlIGluIHNlbGZbcG9zXS5zcGFjZS5rZXlzKCldKQogICAgICAgICAgICAgICAgICAgIGlmIG5vdCBzZXQoc2VsZltuYl0uc3BhY2Uua2V5cygpKS5pc3N1YnNldChhdmFpbGFibGUpOgogICAgICAgICAgICAgICAgICAgICAgICBhdmFpbGFibGUgPSBhdmFpbGFibGUgJiBzZXQoc2VsZltuYl0uc3BhY2Uua2V5cygpKQogICAgICAgICAgICAgICAgICAgICAgICBpZiBsZW4oYXZhaWxhYmxlKSA9PSAwOgogICAgICAgICAgICAgICAgICAgICAgICAgICAgcmV0dXJuIHNlbGYuYmFja3RyYWNrKCkKCiAgICAgICAgICAgICAgICAgICAgICAgIGVsaWYgc2VsZi5TdGFjayBhbmQgKG5iIG5vdCBpbiBzZWxmLlN0YWNrWy0xXS5rZXlzKCkpOgogICAgICAgICAgICAgICAgICAgICAgICAgICAgIyBQdXNoIHRoaXMgY2hhbmdlZCBLbm90IGludG8gdGhlIFN0YWNrLgogICAgICAgICAgICAgICAgICAgICAgICAgICAgc2VsZi5TdGFja1stMV1bbmJdID0gc2VsZltuYl0uc3BhY2UuY29weSgpCiAgICAgICAgICAgICAgICAgICAgICAgIHNlbGZbbmJdID0gS25vdCh7c3RhdGU6IHNlbGYud2VpZ2h0c1tzdGF0ZV0gZm9yIHN0YXRlIGluIGF2YWlsYWJsZX0pCiAgICAgICAgICAgICAgICAgICAgICAgIFByb3BhZ1N0YWNrLmFwcGVuZChuYikKICAgICAgICAgICAgICAgICAgICAgICAgY2hhbmdlZC5hZGQobmIpCiAgICAgICAgcmV0dXJuIGNoYW5nZWQKCiAgICBkZWYgYmFja3RyYWNrKHNlbGYpOgogICAgICAgICIiIkJhY2t0cmFja3MgdG8gdGhlIHByZXZpb3VzIHN0ZXAuIAogICAgICAgIElmIHRoZXJlIGlzIG5vIHdheSB0byBiYWNrdHJhY2sgdGhlbiB0aGlzIG1ldGhvZCByYWlzZXMgQ29sbGFwc2VFcnJvci4gIiIiCiAgICAgICAgcHJpbnQoJzAnKQogICAgICAgIGlmIGxlbihzZWxmLlN0YWNrKToKICAgICAgICAgICAgc3RlcCA9IHNlbGYuU3RhY2sucG9wKCkKICAgICAgICAgICAgIyBSZXN0b3JlIGFsbCB0aGUgS25vdCBhZmZlY3RlZCBieSB0aGUgbGFzdCBjb2xsYXBzZS4KICAgICAgICAgICAgZm9yIChwb3NpdGlvbiwgc3BhY2UpIGluIHN0ZXAuaXRlbXMoKToKICAgICAgICAgICAgICAgIHNlbGZbcG9zaXRpb25dID0gS25vdChzcGFjZSkKICAgICAgICAgICAgICAgIHNlbGYud2FpdF90b19jb2xsYXBzZS5hZGQocG9zaXRpb24pCiAgICAgICAgICAgIHJldHVybiBzZXQoc3RlcC5rZXlzKCkpCiAgICAgICAgZWxzZToKICAgICAgICAgICAgcmFpc2UgQ29sbGFwc2VFcnJvcigiTm8gU3Vsb3Rpb24iKQoKICAgIGRlZiBvYnNlcnZlKHNlbGYsIHN1cnZlaWwpOgogICAgICAgICcnJ09ic2VydmUgdGhlIHdob2xlIFdhdmVGdW5jdGlvbicnJwogICAgICAgIHRyeToKICAgICAgICAgICAgaWYgc3VydmVpbDoKICAgICAgICAgICAgICAgIHdoaWxlIHNlbGYud2FpdF90b19jb2xsYXBzZToKICAgICAgICAgICAgICAgICAgICB5aWVsZCBzZWxmLmNvbGxhcHNlKHNlbGYubWluX2VudHJvcHlfcG9zKCkpCiAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICB3aGlsZSBzZWxmLndhaXRfdG9fY29sbGFwc2U6CiAgICAgICAgICAgICAgICAgICAgbGlzdChzZWxmLmNvbGxhcHNlKHNlbGYubWluX2VudHJvcHlfcG9zKCkpKQogICAgICAgICAgICAgICAgeWllbGQgWyh4LCB5KSBmb3IgeCBpbiByYW5nZShzZWxmLnNpemVbMF0pIGZvciB5IGluIHJhbmdlKHNlbGYuc2l6ZVsxXSldCiAgICAgICAgZXhjZXB0IENvbGxhcHNlRXJyb3I6CiAgICAgICAgICAgIHJhaXNlIENvbGxhcHNlRXJyb3IKCmlmIF9fbmFtZV9fID09ICJfX21haW5fXyI6CiAgICBkZWYgTWF0cml4UHJvY2Vzc29yKGVudHJ5LCBzaXplLCBOLCBvcHRpb25zKToKICAgICAgICBkZWYgdXBkYXRlKG1hdHJpeCwgcG9zaXRpb24sIHcsIE4pOgogICAgICAgICAgICBsaW1pdF9pID0gTiBpZiBwb3NpdGlvblswXSA9PSB3LnNpemVbMF0gLSAxIGVsc2UgMQogICAgICAgICAgICBsaW1pdF9qID0gTiBpZiBwb3NpdGlvblsxXSA9PSB3LnNpemVbMV0gLSAxIGVsc2UgMQogICAgICAgICAgICBmb3IgaSBpbiByYW5nZShsaW1pdF9pKToKICAgICAgICAgICAgICAgIGZvciBqIGluIHJhbmdlKGxpbWl0X2opOgogICAgICAgICAgICAgICAgICAgIG1hdHJpeFtwb3NpdGlvblswXSArIGldW3Bvc2l0aW9uWzFdICsgal0gPSB3LnBhdHRlcm5zW2xpc3Qod1twb3NpdGlvbl0uc3BhY2Uua2V5cygpKVswXV1baV1bal0KICAgICAgICAgICAgcmV0dXJuIG1hdHJpeAoKICAgICAgICB3ID0gV2F2ZUZ1bmN0aW9uKHNpemUsIGVudHJ5LCBOPU4sICoqb3B0aW9ucykKICAgICAgICBtYXRyaXggPSBbW05vbmVdICogc2l6ZVswXSBmb3IgXyBpbiByYW5nZShzaXplWzFdKV0KCiAgICAgICAgZm9yIGNoYW5nZWQgaW4gdy5vYnNlcnZlKHcub3B0aW9uc1snc3VydiddKToKICAgICAgICAgICAgZm9yIHBvcyBpbiBjaGFuZ2VkOgogICAgICAgICAgICAgICAgbWF0cml4ID0gdXBkYXRlKG1hdHJpeCwgcG9zLCB3LCBOKQogICAgICAgIGZvciBlYWNobGluZSBpbiBtYXRyaXg6CiAgICAgICAgICAgIHByaW50KGVhY2hsaW5lKQoKICAgICMgVGhpcyBpcyBhIGRlbW8gdG8gc2hvdyBhIGhvdyB3ZmMgaXMgd29ya2luZyBvbiBzdHJpbmcgbWF0cml4LgogICAgIyBJbWFnaW5lIHRoYXQgYmVsb3cgaXMgYSBtYXAsIHdoZXJlICdMJyA9IGxhbmQsICdDJyA9IGNvYXN0LCAnUycgPSBzZWEsCiAgICAjIGFuZCBub3cgd2Ugd2lsbCBzaG93IHlvdSB0aGF0IGhvdyB3ZmMgZ2VuZXJhdGUgbWFwcyB3aXRoIHNvbWUgbmF0dXJhbCBydWxlcywgc3VjaCBhcyBsYW5kIGNhbm5vdCBiZSBuZXh0IHRvIHNlYS4KICAgIGVudHJ5ID0gKAogICAgICAgICgnTCcsICdMJywgJ0wnLCAnTCcsICdMJywgJ0wnLCAnTCcpLAogICAgICAgICgnTCcsICdMJywgJ0MnLCAnTCcsICdMJywgJ0wnLCAnTCcpLAogICAgICAgICgnQycsICdDJywgJ1MnLCAnQycsICdDJywgJ0wnLCAnTCcpLAogICAgICAgICgnUycsICdTJywgJ1MnLCAnUycsICdTJywgJ0MnLCAnTCcpLAogICAgICAgICgnUycsICdTJywgJzozJywgJ1MnLCAnUycsICdTJywgJ0MnKQogICAgKQogICAgb3B0aW9ucyA9IHsgICAgICAgIAogICAgICAgICdBbGxSdWxlcyc6MCwKICAgICAgICAnc3VydmVpbCc6MCwKICAgICAgICAnUGVyaW9kaWNJbnB1dCc6MCwKICAgICAgICAnUGVyaW9kaWNPdXRwdXQnOjAsCiAgICAgICAgJ1JvdGF0aW9uJzowLAogICAgICAgICdSZWZsZWN0aW9uJzowCiAgICB9CiAgICBNYXRyaXhQcm9jZXNzb3IoZW50cnksICgxMCwxMCksTj0xLG9wdGlvbnM9b3B0aW9ucyk=