class Node:
    def __init__(self, L, j, children):
        self.L, self.i, self.children = L, j, children
    def __repr__(self): return str((self.L, self.i, self.children))

class GSS:
    def __init__(self): self.gss, self.P = {}, {}

    def get(self, L, i, children):
        my_label = (L, i)
        if my_label not in self.gss:
            self.gss[my_label] = Node(L, i, children)
            assert my_label not in self.P
            self.P[my_label] = []
        return self.gss[my_label]

    def add_to_P(self, u, j):
        label = (u.L, u.i)
        self.P[label].append(j)

    def __repr__(self): return str(self.gss)

class GLLParser:
    def create(self, L, u, j):
        v = self.gss.get(L, j, [u])
        if u not in v.children:
            v.children.append(u)
            label = (L, j)
            for k in self.gss.P[label]:
                self.add(L, u, k)
        return v

    def add(self, L, u, j):
        if (L, u) not in self.U[j]:
            self.U[j].append((L, u))
            assert (L,u,j) not in self.R
            self.R.append((L, u, j))

    def pop(self, u, j):
        if u != self.u0:
            self.gss.add_to_P(u, j)
            for v in u.children:
                self.add(u.L, v, j)
        return u


    def __init__(self, input_str):
        self.R = []
        self.gss = GSS()
        self.I = input_str
        self.m = len(self.I) # |I| + 1
        self.u1 = self.gss.get('L0', 0, [])
        self.u0 = self.gss.get('$', self.m, [])
        self.u1.children.append(self.u0)

        self.U = []
        for j in range(self.m): # 0<=j<=m
            self.U.append([]) # U_j = empty