



class State:
    def __init__(self,x, parent = None):
        self.x = x[:]
        self.parent = parent
        self.action = None

    def expand(self):
        result = []
        #Vx
        for i in range( len(self.x) ):
            if self.x[i] > 0:
                child = State(self.x, self)
                child.x[i] = 0
                child.action = "V" + str(i)
                result.append( child )
        #Nx:
        for i in range(len(self.x)):
            if self.x[i] < V[i]:
                child = State(self.x, self)
                child.x[i] = V[i]
                child.action = "N" + str(i)
                result.append( child )
        #iPj
        for i in range(len(self.x)):
            for j in range(len(self.x)):
                if i == j:
                    continue
                else:
                    if self.x[j] != V[j]:
                        child = State(self.x, self)
                        vol = self.x[i] + self.x[j]
                        over = vol - V[j]
                        if over < 0:
                            over = 0
                        child.x[j] = vol - over
                        child.x[i] = over
                        child.action = str(i) + "P" + str(j)
                        result.append(child)
        return result

V = [5,3,4,2]

start = State([5,0,0,1])
res = start.expand()

Q = [ start ]
known = {}
known[ str(start.x) ] = 1

while len(Q) > 0:
    actual = Q.pop()
    
    if actual.x == [4,0]:
        print("HURA")
        path = []
        while actual != None:
            path.append( actual.action )
            actual = actual.parent
        p2 = path[::-1]
        print(p2[1:])
        break

    for child in actual.expand():
        if not str(child.x) in known:
            Q.insert(0, child)
            known[ str(child.x) ] = True