산타의 선물공장 - 코드트리

크리스마스가 얼마 남지 않아 마음이 급해진 산타는 선물 공장을 세웠습니다. 산타는 공장에서 순서대로 q개의 명령에 따라 일을 진행합니다. 일의 종류는 크게 다음 5가지로 나뉩니다.

1. 공장 설립

선물 공장에 m개의 벨트를 설치하고, 각 벨트 위에 정확히 mn​개의 물건들이 놓아 총 n개의 물건을 준비합니다. <Figure 1>은 n이 12이고 m이 3인 예입니다.

각 물건에는 고유한 번호(ID)와 무게(W)가 적혀있습니다. 번호는 상자마다 다르지만, 무게가 동일한 상자는 있을 수 있습니다.

2. 물건 하차

산타가 원하는 상자의 최대 무게인 w_max가 주어집니다. 1번부터 m번까지 순서대로 벨트를 보며 각 벨트의 맨 앞에 있는 선물 중 해당 선물의 무게가 w_max 이하라면 하차를 진행하고, 그렇지 않다면 해당 선물을 벨트 맨 뒤로 보냅니다. 벨트에 있던 상자가 빠지면 한 칸씩 앞으로 내려와야 함에 유의합니다.

예로 <Figure 2>에서 w_max가 25인 명령이 주어졌다면, 1번 컨베이어 벨트에 있던 상자는 뒤로 보내지지만 2, 3번 컨베이어 벨트에 있던 상자는 하차를 하게 됩니다. 이 명령에서는 과정을 진행한 후 하차된 상자 무게의 총 합인 35를 출력해야 합니다.

3. 물건 제거

산타가 제거하기를 원하는 물건의 고유 번호 r_id가 주어집니다. 해당 고유 번호에 해당하는 상자가 놓여있는 벨트가 있다면, 해당 벨트에서 상자를 제거하고 이에 따라 뒤에 있던 상자들은 앞으로 한 칸씩 내려오게 됩니다.

예로 <Figure 3>에서 r_id가 22인 명령이 주어졌다면 2번째 벨트에 있는 ID 22에 해당하는 상자를 제거하게 됩니다. 이 명령에서는 그러한 상자가 있는 경우 r_id값을, 없다면 -1을 출력해야 합니다.

4. 물건 확인

산타가 확인하기를 원하는 물건의 고유 번호 f_id가 주어집니다. 이 명령에서는 해당 고유 번호에 해당하는 상자가 놓여있는 벨트가 있다면 해당 벨트의 번호를 출력하고, 없다면 -1을 출력합니다. 단, 상자가 있는 경우, 해당 상자 위에 있는 모든 상자를 전부 앞으로 가져옵니다. 가져올 시 순서는 그대로 유지가 되어야 함에 유의합니다.

예로 <Figure 4>에서 f_id가 14인 명령이 주어졌다면 -1을, f_id가 18인 명령이 주어졌다면 상자가 놓여있는 벨트의 번호인 3을 출력하고 18번 위에 있는 모든 상자를 앞으로 당겨줍니다. 여기서는 18번 상자만 옮겨지게 됩니다.

5. 벨트 고장

고장이 발생한 벨트의 번호 b_num이 주어집니다. b_num번째 벨트에 고장이 발생하면 해당 벨트는 다시는 사용할 수 없게 되고, b_num 벨트의 바로 오른쪽 벨트부터 순서대로 보며 아직 고장이 나지 않은 최초의 벨트 위로 b_num 벨트에 놓여 있던 상자들을 아래에서부터 순서대로 하나씩 옮겨줍니다. 만약 m번 벨트까지 봤는데도 고장나지 않은 벨트가 없다면 다시 1번부터 순서대로 벨트를 확인하여, 이 명령이 주어졌을 때에는 b_num번째 벨트를 제외한 벨트 중 최소 하나 이상이 정상 상태임을 가정해도 좋습니다. 즉, 모든 벨트가 망가지는 경우는 없습니다.

예로 <Figure 5>에서 b_num이 3인 명령이 주어졌다면 3번째 벨트는 망가지며, 3번 벨트 위에 있던 모든 상자가 1번 벨트 위로 순서대로 올라가게 됩니다. 이 명령을 수행하기 전 만약 b_num 벨트가 이미 망가져 있었다면 -1을, 그렇지 않았다면 정상적으로 고장을 처리했다는 뜻으로 b_num 값을 출력합니다.

산타가 q번에 걸쳐 명령을 순서대로 진행하며 원하는 결과를 출력하는 프로그램을 작성해보세요.

입력 형식

첫 번째 줄에 명령의 수 q가 주어집니다.

두 번째 줄부터는 q개의 줄에 걸쳐 명령의 정보가 주어집니다. 각 명령에 따른 형태는 다음과 같습니다.

• 공장 설립
• 100 n m ID1 ID2 ... IDn W1 W2 ... Wn 형태로 공백을 사이에 두고 주어집니다. 이는 m개의 벨트와 n개의 선물로 이루어진 공장을 세우며, 선물을 주어진 순서대로 mn​개씩 잘라 1번 벨트부터 m번 벨트까지 올려줍니다. 이 명령은 항상 첫 번째 명령으로만 주어지며, 항상 주어집니다. 또한, 이 명령에 대해서는 출력할 값이 없습니다.
• 물건 하차
• 200 w_max 형태로 공백을 사이에 두고 주어집니다. 이 명령에서는 하차된 상자 무게의 총 합을 출력해야 합니다.
• 물건 제거
• 300 r_id 형태로 공백을 사이에 두고 주어집니다. 이 명령에서는 그러한 상자가 있는 경우 r_id값을, 없다면 -1을 출력해야 합니다.
• 물건 확인
• 400 f_id 형태로 공백을 사이에 두고 주어집니다. 이 명령에서는 그러한 상자가 있는 경우 f_id값을, 없다면 -1을 출력해야 합니다. 이 명령에서는 해당 고유 번호에 해당하는 상자가 놓여있는 벨트가 있다면 해당 벨트의 번호를 출력하고, 없다면 -1을 출력합니다.
• 벨트 고장
• 500 b_num 형태로 공백을 사이에 두고 주어집니다. 이 명령을 수행하기 전 만약 b_num 벨트가 이미 망가져 있었다면 -1을, 그렇지 않았다면 정상적으로 고장을 처리했다는 뜻으로 b_num 값을 출력합니다.

• 1 ≤ q ≤ 100,000
• 1 ≤ n ≤ 100,000
• 1 ≤ m ≤ 10, n은 항상 m의 배수
• 1 ≤ ID ≤ 1,000,000,000
• 1 ≤ W ≤ 1,000,000,000
• 1 ≤ r_id, f_id ≤ 1,000,000,000
• 1 ≤ b_num ≤ m

출력 형식

산타가 q개의 명령을 진행하면서 출력해야 하는 값을 한 줄에 하나씩 출력합니다.

예제

입력	출력
7 100 12 3 10 12 20 15 14 19 22 25 16 17 21 18 30 30 20 20 10 18 17 15 25 11 14 17 200 25 300 22 300 999 400 14 400 18 500 3	35 22 -1 -1 3 3
12 100 12 3 10 12 20 15 14 19 22 25 16 17 21 18 30 30 20 20 10 18 17 15 25 11 14 17 200 25 300 22 300 999 400 14 400 18 500 3 200 5 300 12 500 1 500 3 200 40	35 22 -1 -1 3 3 0 12 1 -1 15
13 100 12 3 10 12 20 15 14 19 22 25 16 17 21 18 30 30 20 20 10 18 17 15 25 11 14 17 200 25 300 22 300 999 400 14 400 18 500 3 400 17 200 15 300 12 500 1 500 3 200 40	35 22 -1 -1 3 3 1 11 12 1 -1 15

제한

시간 제한: 1000ms

메모리 제한: 120MB

풀이

q = int(input())    # 명령의 수
n,m = None, None    # n개의 선물, m개의 벨트
belts = {}

for _ in range(q):
    res = 0
    cmd = list(map(int, input().split()))
    
    # 공장 설립
    if cmd[0]==100:
        n,m = cmd[1], cmd[2]
        broken = [False]*m  # 각 벨트 고장 여부
        n_m = n//m  # 벨트당 상자 수
        head, tail = [-1]*m, [-1]*m # 벨트마다 맨앞 맨뒤인 상자의 ID 기록
         # 각 벨트마다 상자 ID : [순서, 무게, 현위치, 변경여부] 저장
        for i in range(m):
            prev = -1
            for index, ID in enumerate(cmd[3 + i*n_m : 3 + i*n_m + n_m]):
                belts[ID] = [i, cmd[3 + n+i*n_m + index], prev, -1]
                if prev!=-1:
                    belts[prev][3] = ID
                prev = ID
                if index==0:
                    head[i] = ID
                elif index==(n_m-1):
                    tail[i] = ID
            
                
    # 물건 하차
    elif cmd[0]==200:
        w_max = cmd[1]
        # 벨트 차례로 확인
        for i in range(m):
            if broken[i]==False and head[i]!=-1:
                # 맨앞 상자가 최대 무게 w_max 이하이면 하차
                if belts[head[i]][1] <= w_max:
                    res += belts[head[i]][1]
                    belts[head[i]][0] = -1 # 벨트에서 내려간 애들 0번째 원소 = -1
                    # head 갱신
                    head[i] = belts[head[i]][3]
                    if head[i]!=-1:
                        belts[head[i]][2] = -1 
                elif head[i]!=tail[i]:
                    # 해당 물건 맨 뒤로 보내기
                    tmp_head = head[i]
                    tmp_tail = tail[i]
                    cur_head = belts[tmp_head][3]
                    belts[tmp_tail][3] = tmp_head
                    belts[tmp_head][2] = tmp_tail
                    belts[tmp_head][3] = -1
                    belts[cur_head][2] = -1
                    head[i] = cur_head
                    tail[i] = tmp_head
        print(res)


    # 물건 제거
    elif cmd[0]==300:
        r_id = cmd[1]
        if r_id not in belts or belts[r_id][0]==-1: # belts에 없다면
            print(-1)
        else:
            cur_belt = belts[r_id][0]
            belts[r_id][0] = -1 # 벨트 번호 -1로 바꾸기
            # 원소 1개인 경우
            if head[cur_belt]==tail[cur_belt]:
                head[cur_belt] = -1
                tail[cur_belt] = -1
            # head인 경우
            if head[cur_belt]==r_id:
                # head 갱신
                belts[belts[r_id][3]][2] = -1
                head[cur_belt] = belts[r_id][3]
            # tail인 경우
            elif tail[cur_belt]==r_id:
                belts[belts[r_id][2]][3] = -1
                tail[cur_belt] = belts[r_id][2]
            # 중간 물건인 경우
            else:
                prev = belts[r_id][2]
                nxt = belts[r_id][3]
                # prev 원소 처리
                belts[prev][3] = nxt
                # next 원소 처리
                belts[nxt][2] = prev
            print(r_id)
        

    # 물건 확인
    elif cmd[0]==400:
        f_id = cmd[1]
        if f_id not in belts or belts[f_id][0]==-1: # belts에 없다면
            print(-1)
        else:
            cur_belt = belts[f_id][0]
            print(cur_belt+1)
            # head인 경우
            if head[cur_belt]==f_id:
                pass
            # tail인 경우
            elif tail[cur_belt]==f_id:
                tail[cur_belt] = belts[f_id][2]
                belts[f_id][2] = -1
                belts[f_id][3] = head[cur_belt]
                belts[tail[cur_belt]][3] = -1
                belts[head[cur_belt]][2] = f_id
                head[cur_belt] = f_id
            # 중간 물건인 경우
            else:
                tmp_tail = tail[cur_belt]       
                tail[cur_belt] = belts[f_id][2]
                belts[tail[cur_belt]][3] = -1
                belts[f_id][2] = -1
                belts[tmp_tail][3] = head[cur_belt]
                belts[head[cur_belt]][2] = tmp_tail
                head[cur_belt] = f_id
        
    
    # 벨트 고장
    elif cmd[0]==500:
        b_num = cmd[1]
        if broken[b_num-1]==True:
            print(-1)
        else:
            broken[b_num-1]=True
            if head[b_num-1]!=-1:
                next_b_num = b_num%m
                while(True):
                    if broken[next_b_num]==False:
                        break
                    next_b_num = (next_b_num+1)%m
                belts[tail[next_b_num]][3] = head[b_num-1]
                belts[head[b_num-1]][2] = tail[next_b_num]
                # head부터 쭉 옮기기
                cur = head[b_num-1]
                while(True):
                    belts[cur][0] = next_b_num
                    if belts[cur][3]==-1:
                        break
                    cur = belts[cur][3]
                tail[next_b_num] = cur
                head[b_num-1] = -1
                tail[b_num-1] = -1
                    
            print(b_num)