class doubleLinkedListElement():
    def __init__(self):
        self.value = None
        self.next = None
        self.prev = None

class doubleLinkedList():
    def __init__(self):
        self.start = None
        self.end = None

    def insert(self, x, idx = "end"):
        order = doubleLinkedListElement()
        order.value = x
        if self.start:
            if idx == "end":
                self.end.next = order
                order.prev = self.end
                self.end = order
            else:
                cur = self.start
                i = 1
                while i < idx-1:
                    cur = cur.next
                    i += 1
                order.prev = cur
                order.next = cur.next
                cur.next.prev = order
                cur.next = order
        else:
            self.start = order
            self.end = order

    def remove(self, x):
        tmp = self.start

        if tmp.value == x:
            self.start.value = None
            self.start = self.start.next
        else:
            while tmp.next:
                if tmp.next.value == x:
                    if tmp.next.next:
                        tmp.next.value = None
                        tmp.next = tmp.next.next
                    else:
                        tmp.next = None
                        self.end = tmp
                    break
                else:
                    tmp = tmp.next

    def getIdx(self, x):
        cur = self.start
        idx = 1
        while cur is not None:
            if cur.value == x:
                return idx
            else:
                cur = cur.next
                idx += 1
        else:
            return -1

    def getValue(self, x):
        cur = self.start
        idx = 1
        while cur is not None:
            if idx == x:
                return cur.value
            else:
                idx += 1
                cur = cur.next
#insert(x, n), remove(x), getIdx(x), getValue(x)

class Stack2:
    def __init__(self):
        self.myStack = doubleLinkedList()

    def push(self, n):
        self.myStack.insert(n)

    def pop(self):
        cur = self.myStack.end.prev
        self.myStack.end.value = None
        cur.next = None
        self.myStack.end = cur

    def size(self):
        idx = 1
        cur = self.myStack.start
        while cur.next is not None:
            idx += 1
            cur = cur.next
        return idx

    def empty(self):
        if self.myStack.start is None:
            return True
        else:
            return False

    def top(self):
        return self.myStack.end.value

class myDatabase:
    '''
    해싱을 구현합니다
    '''

    def __init__(self, size) :
        '''
        dictionary를 이용합니다.

        이곳은 수정하지 마세요.
        '''
        self.myData = {}

    def put(self, key, value) :
        '''
        (key, value)를 저장합니다.
        '''
        self.myData[key] = value

    def get(self, key) :
        '''
        key에 해당하는 value를 반환합니다. 만약 key에 해당하는 value가 없다면 -1을 반환합니다.
        '''
        if key in self.myData:
            return self.myData[key]
        else:
            return -1
        #return self.myData.get(key, -1)

class orderInfo:
    '''
    이 부분은 수정하지 마세요.
    '''
    def __init__(self, t, d, v):
        self.time = t
        self.duration = d
        self.vip = v

def processOrder(orders) :
    '''
    주문 정보가 주어질 때, 주문이 처리되는 순서를 출력합니다.
    '''
    process = []
    result = []
    for i in range(len(orders)):
        if result is None:
            result.append(i+1)
            process.append(orders[i].time)
        else:
            result.append(i+1)
            process.append(max(orders[i-1].time + orders[i-1].duration, orders[i].time))

    for i in range(len(orders)):
        j = 1
        count = 0
        if orders[i].vip == 1:
            while j < i:
                if orders[j].vip == 0 and process[j] > orders[i].time :
                    result[j] = result[j]+1
                    process[i] = min(process[i], process[j])
                    if j == 1:
                        process[j] = process[i] + orders[i].duration
                    else:
                        process[j] = max(process[j-1]+orders[j-1].duration, orders[j].time)
                    j += 1
                    count += 1
                else:
                    j += 1
            result[i] = result[i] - count
            i += 1
        else:
            i += 1

    return result;



def processOrder(orders):
    result = []
    result2 = []
    vipQue = []
    normQue = []

    for i in range(len(orders)):
        if orders[i].vip == 0:
            if normQue is None:
                normQue.append([i+1, orders[i].time])
            else:
                tmp = max(normQue[-1][1] + orders[normQue[-1][0]-1].duration, orders[i].time) #왜 index out of range ㅇ에러가 ....!?
                normQue.append([i+1, tmp])
        else:
            if vipQue is None:
                vipQue.append([i+1, orders[i].time])
            else:
                tmp = max(vipQue[-1][1] + orders[vipQue[-1][0]-1].duration, orders[i].time)
                vipQue.append([i+1, tmp])

    for i in range(len(vipQue)):
        for j in range(len(normQue)):
            if vipQue[i][1] <= normQue[j][1]:
                result.append(vipQue[i][0])
            else:
                result.append(normQue[i][0])

    for i in range(len(result)):
        result2.append(result.index(i+1)+1)




data1 = orderInfo(1,4,0)
data2 = orderInfo(3,1,0)
data3 = orderInfo(4,1,0)
data4 = orderInfo(5,4,1)
data5 = orderInfo(6,5,0)
data6 = orderInfo(7,4,0)
data7 = orderInfo(9,4,1)
data8 = orderInfo(13,4,1)
data9 = orderInfo(17,4,1)

orders = [data1, data2, data3, data4, data5, data6, data7, data8, data9]

processOrder(orders)