"""
출처:프로그래머스,
https://school.programmers.co.kr/learn/courses/30/lessons/150366
"""

# 풀이 과정
# 이후 (r1, c1) 와 (r2, c2) 중 어느 위치를 선택하여도 병합된 셀로 접근합니다. 중요포인트
#  병합된 셀의 경우 따로 체크 리스트를 만든 후 병합과 삭제 시 따로 함수를 만들어서 구현! (시간과 효율성에 관하여 생각도 해보기!) 03 07 20시 추가!
# 업데이트 된 셀 또한 통합이 되어있을 경우 통째로 바뀌어야 한다!
from collections import deque


def merge(m, s, fir, sec, check):
    check = deque(check)
    flag = False
    n = len(check)
    count = 0
    r1 = fir[0]
    c1 = fir[1]
    r2 = sec[0]
    c2 = sec[1]
    new = [[r1, c1], [r2, c2]]
    while count < n:
        i = check.popleft()
        if [r1, c1] in i or [r2, c2] in i:
            for v, w in i:
                if not [v, w] in new:
                    new.append([v, w])
            flag = True
        else:
            check.append(i)

        count += 1

    if flag == False:
        check.append([[r1, c1], [r2, c2]])
        m[r1][c1] = s
        m[r2][c2] = s
    else:
        for v, w in new:
            m[v][w] = s
        check.append(new)

    return m, list(check)


def unmerge(m, check, s, fir):
    r = fir[0]
    c = fir[1]
    check = deque(check)
    n = len(check)
    count = 0

    while count < n:
        i = check.popleft()

        if [r, c] in i:
            for v, w in i:
                m[v][w] = "EMPTY"

            m[r][c] = s
            break

        check.append(i)

        count += 1

    m[r][c] = s

    return m, list(check)


def solution(commands):
    m = [["EMPTY"] * 50 for _ in range(50)]  # 표

    k = commands  # 축약

    check = []  # sum cell
    result = []

    for i in k:
        # update
        if "UPDATE" in i:
            if i.count(" ") == 3:
                t = i.split(" ")
                r = int(t[1]) - 1
                c = int(t[2]) - 1
                value = t[3]

                for v in check:
                    if [r, c] in v:
                        # print(check,value)
                        for a, b in v:
                            m[a][b] = value

                        break
                else:
                    m[r][c] = value

            elif i.count(" ") == 2:
                t = i.split(" ")
                value1 = t[1]
                value2 = t[2]
                # 모든 셀 변환
                for v1 in range(50):
                    for v2 in range(50):
                        if m[v1][v2] == value1:
                            m[v1][v2] = value2

        # merge
        elif "MERGE" in i and not "UN" in i:
            t = i.split(" ")
            # index를 위해 -1
            r1 = int(t[1]) - 1
            c1 = int(t[2]) - 1
            r2 = int(t[3]) - 1
            c2 = int(t[4]) - 1

            fir = [r1, c1]
            sec = [r2, c2]

            if m[r1][c1] == "EMPTY":
                s = m[r2][c2]
            else:
                s = m[r1][c1]
            # print(check,"before",s)
            m, check = merge(m, s, fir, sec, check)
            # print(check,"after",s)

        # unmerge
        elif "UNMERGE" in i:
            t = i.split(" ")
            r = int(t[1]) - 1
            c = int(t[2]) - 1
            s = m[r][c]
            # print(s,[r,c])
            fir = [r, c]
            m, check = unmerge(m, check, s, fir)

        elif "PRINT" in i:
            t = i.split(" ")
            r = int(t[1]) - 1
            c = int(t[2]) - 1
            result.append(m[r][c])

        # print(check,"all",t[0])

    return result