from copy import deepcopy
from bisect import bisect

def unique_lcs(a, b):
    # set index[line in a] = position of line in a unless
    # unless a is a duplicate, in which case it's set to None
    index = {}
    for i in xrange(len(a)):
        line = a[i]
        if line in index:
            index[line] = None
        else:
            index[line]= i
    # make btoa[i] = position of line i in a, unless
    # that line doesn't occur exactly once in both, 
    # in which case it's set to None
    btoa = [None] * len(b)
    index2 = {}
    for pos, line in enumerate(b):
        next = index.get(line)
        if next is not None:
            if line in index2:
                # unset the previous mapping, which we now know to
                # be invalid because the line isn't unique
                btoa[index2[line]] = None
                del index[line]
            else:
                index2[line] = pos
                btoa[pos] = next
    # this is the Patience sorting algorithm
    # see http://en.wikipedia.org/wiki/Patience_sorting
    backpointers = [None] * len(b)
    stacks = []
    lasts = []
    k = 0
    for bpos, apos in enumerate(btoa):
        if apos is None:
            continue
        # as an optimization, check if the next line comes at the end,
        # because it usually does
        if stacks and stacks[-1] < apos:
            k = len(stacks)
        # as an optimization, check if the next line comes right after
        # the previous line, because usually it does
        elif stacks and stacks[k] < apos and (k == len(stacks) - 1 or stacks[k+1] > apos):
            k += 1
        else:
            k = bisect(stacks, apos)
        if k > 0:
            backpointers[bpos] = lasts[k-1]
        if k < len(stacks):
            stacks[k] = apos
            lasts[k] = bpos
        else:
            stacks.append(apos)
            lasts.append(bpos)
    if len(lasts) == 0:
        return []
    result = []
    k = lasts[-1]
    while k is not None:
        result.append((btoa[k], k))
        k = backpointers[k]
    result.reverse()
    return result

assert unique_lcs('', '') == []
assert unique_lcs('a', 'a') == [(0, 0)]
assert unique_lcs('a', 'b') == []
assert unique_lcs('ab', 'ab') == [(0, 0), (1, 1)]
assert unique_lcs('abcde', 'cdeab') == [(2, 0), (3, 1), (4, 2)]
assert unique_lcs('cdeab', 'abcde') == [(0, 2), (1, 3), (2, 4)]
assert unique_lcs('abXde', 'abYde') == [(0, 0), (1, 1), (3, 3), (4, 4)]
assert unique_lcs('acbac', 'abc') == [(2, 1)]

def recurse_matches(a, b, ahi, bhi, answer, maxrecursion):
    # this will never happen normally, this check is to prevent DOS attacks
    if maxrecursion < 0:
        return
    oldlength = len(answer)
    if len(answer) == 0:
        alo, blo = 0, 0
    else:
        alo, blo = answer[-1]
        alo += 1
        blo += 1
    # extend individual line matches into match sections
    for apos, bpos in unique_lcs(a[alo:ahi], b[blo:bhi]):
        apos += alo
        bpos += blo
        if len(answer) == 0:
            lasta = -1
            lastb = -1
        else:
            lasta, lastb = answer[-1]
        # don't overlap with an existing match
        if apos <= lasta or bpos <= lastb:
            continue
        # extend match as far back as possible
        while apos > lasta + 1 and bpos > lastb + 1:
            newapos = apos - 1
            while newapos > lasta and a[newapos] is None:
                newapos -= 1
            if newapos == lasta or a[newapos] != b[bpos - 1]:
                break
            apos = newapos
            bpos -= 1
        recurse_matches(a, b, apos, bpos, answer, maxrecursion - 1)
        answer.append((apos, bpos))
        # extend match as far forward as possible
        while apos < ahi - 1 and bpos < bhi - 1:
            newapos = apos + 1
            while newapos < ahi and a[newapos] is None:
                newapos += 1
            if newapos == ahi or a[newapos] != b[bpos + 1]:
                break
            apos = newapos
            bpos += 1
            answer.append((apos, bpos))
    if len(answer) > oldlength:
        # find matches between the last match and the end
        recurse_matches(a, b, ahi, bhi, answer, maxrecursion - 1)

a1 = []
recurse_matches(['a', None, 'b', None, 'c'], ['a', 'a', 'b', 'c', 'c'], 5, 5, a1, 10)
assert a1 == [(0, 1), (2, 2), (4, 3)]
a2 = []
recurse_matches(['a', 'c', 'b', 'a', 'c'], ['a', 'b', 'c'], 5, 3, a2, 10)
assert  a2 == [(0, 0), (2, 1), (4, 2)]

class LivingStatus:
    def __init__(self, overrides):
        self.overrides = overrides
    
    def merge(self, other):
        newdict = {}
        for (key, value) in self.overrides.items():
            newdict[key] = value
            assert other.overrides.get(key, value) == value
        for (key, value) in other.overrides.items():
            newdict[key] = value
            assert self.overrides.get(key, value) == value
        return LivingStatus(newdict)

    def is_living(self):
        oldworking = set()
        newworking = set(self.overrides.keys())
        while oldworking != newworking:
            oldworking = newworking
            newworking = set(self.overrides.keys())
            for k in oldworking:
                for j in self.overrides[k]:
                    newworking.discard(j)
        return 'root' not in newworking

    def _makes_living(self, key):
        result = False
        while key != 'root':
            result = not result
            key = self.overrides[key][0]
        return result

    def set_living(self, revision, new_status):
        if new_status == self.is_living():
            return self
        alive = set(self.overrides.keys())
        for i in self.overrides.values():
            for j in i:
                alive.discard(j)
        newdict = deepcopy(self.overrides)
        newdict[revision] = [a for a in alive if self._makes_living(a) != new_status]
        return LivingStatus(newdict)

ds = LivingStatus({'root': []})

assert not ds.is_living()
ta = ds.set_living('a', True)
assert ta.is_living()
tb = ds.set_living('b', True)
tc = ta.set_living('c', False)
assert not tc.is_living()
td = ta.set_living('d', False)
te = tb.merge(tc)
assert te.is_living()
tf = te.merge(td)
assert tf.is_living()
tg = tb.set_living('g', False)
th = te.merge(tg)
assert not th.is_living()

def new_file_state(initial, revision):
    result = FileState([(line, (revision, i)) for (i, line) in enumerate(initial)])
    for i, line in enumerate(initial):
        result.states[(revision, i)] = ds.set_living(revision, True)
    return result

class FileState:
    def __init__(self, weave):
        self.weave = weave
        self.states = {}

    def mash(self, other):
        assert self.weave is other.weave
        newstate = FileState(self.weave)
        for key in self.states.keys() + other.states.keys():
            newstate.states[key] = self.states.get(key, ds).merge(other.states.get(key, ds))
        return newstate

    def current(self):
        result = []
        for line, ident in self.weave:
            if self.states.get(ident, ds).is_living():
                result.append(line)
        return result

    def conflict(self, other):
        result = []
        left = []
        right = []
        clean = []
        mustleft = False
        mustright = False
        for line, ident in self.weave:
            meline = self.states.get(ident, ds)
            otherline = other.states.get(ident, ds)
            mehave = meline.is_living()
            otherhave = otherline.is_living()
            mergehave = meline.merge(otherline).is_living()
            if mehave and otherhave and mergehave:
                if mustright and mustleft:
                    result.append((left, right))
                else:
                    result.extend(clean)
                result.append(line)
                left = []
                right = []
                clean = []
                mustleft = False
                mustright = False
            else:
                if mehave != otherhave:
                    if mehave == mergehave:
                        mustleft = True
                    else:
                        mustright = True
                if mehave:
                    left.append(line)
                if otherhave:
                    right.append(line)
                if mergehave:
                    clean.append(line)
        if mustright and mustleft:
            result.append((left, right))
        else:
            result.extend(clean)
        return result

    def resolve(self, result, revision):
        lines = [line for (line, ident) in self.weave]
        for i in xrange(len(lines)):
            if not self.states.get(self.weave[i][1], ds).is_living():
                lines[i] = None
        matches = []
        recurse_matches(lines, result, len(lines), len(result), matches, 10)
        lines = [line for (line, ident) in self.weave]
        matches2 = []
        for a, b in matches + [(len(lines), len(result))]:
            recurse_matches(lines, result, a, b, matches2, 10)
            if a != len(lines):
                matches2.append((a, b))
        living = set()
        for a, b in matches2:
            living.add(self.weave[a][1])
        toinsert = []
        lastb = -1
        lasta = -1
        for a, b in matches2 + [(len(self.weave), len(result))]:
            for x in xrange(lastb + 1, b):
                newline = (revision, x)
                living.add(newline)
                toinsert.append((lasta + 1, (result[x], newline)))
            lasta = a
            lastb = b
        toinsert.reverse()
        for pos, line in toinsert:
            self.weave.insert(pos, line)
        result = FileState(self.weave)
        for line, ident in self.weave:
            result.states[ident] = self.states.get(ident, ds).set_living(revision, ident in living)
        return result

ta = new_file_state(['a', 'b', 'c'], 'x')
assert ta.resolve(['b', 'c', 'd'], 'y').current() == ['b', 'c', 'd']
ta = new_file_state(['a', 'b', 'c'], 'x')
assert ta.resolve(['d', 'a', 'b', 'c'], 'y').mash(ta.resolve(['a', 'b', 'c', 'e'], 'z')).current() == ['d', 'a', 'b', 'c', 'e']
ta = new_file_state(['a', 'b', 'c'], 'x')
assert ta.resolve(['a', 'd', 'c'], 'y').resolve(['a', 'b', 'c'], 'z').conflict(ta.resolve(['a', 'e', 'c'], 'w')) == ['a', 'e', 'c']
ta = new_file_state(['a', 'b', 'c'], 'x')
assert ta.resolve(['a', 'd', 'c'], 'y').conflict(ta.resolve(['a', 'e', 'c'], 'z')) == ['a', (['d'], ['e']), 'c']