가로수

연세대학교에서 대대적인 가로수 심기 작업을 한다. 학교는 이 작업에 예산이 얼마나 필요한지 미리 알아보려 한다.

학교에는 건물이 $N$개 있고, 각 건물 앞에 나무를 정확히 한 그루씩 심는다. 따라서 모두 $N$그루를 심는다. 심는 나무는 항상 두 종류 중 하나다. 하나는 은행나무로, 해충이 꼬이지 않지만 가을에 악취가 심하다. 다른 하나는 플라타너스로, 여름에 그늘을 만들어 주지만 봄에 일부 사람에게 호흡기 알레르기를 일으킬 수 있다.

학교는 건물마다 은행나무를 심을 때의 비용과 플라타너스를 심을 때의 비용을 모두 조사해 두었다. 건물이 있는 자리의 지형과 환경이 다르므로, 같은 종류의 나무라도 건물이 다르면 비용이 다를 수 있다.

학교는 최소 비용으로 모든 건물 앞에 가로수를 심는 계획을 세웠다. 그런데 뒤늦게 합류한 디자이너가 이대로 심으면 미관이 좋지 않다며 계획을 꽤 많이 고쳐야 한다고 했다. 디자이너의 요청은 두 가지 중 하나다.

1. 건물 $i$와 건물 $j$에는 반드시 같은 종류의 나무를 심어야 한다.
2. 건물 $i$와 건물 $j$에는 반드시 다른 종류의 나무를 심어야 한다.

설상가상으로 요청을 반영해 계획을 고치는 일이 오래 걸리는 사이에, 미리 조사해 둔 비용까지 바뀌기 시작했다. 비용은 다음 두 가지 중 하나로 바뀐다.

1. 건물 $i$에 은행나무를 심는 비용이 바뀐다.
2. 건물 $i$에 플라타너스를 심는 비용이 바뀐다.

학교는 계획을 손수 고치는 것이 더는 무리라고 판단하고, 계속 바뀌는 요청과 가격을 실시간으로 반영해 최적의 계획을 찾아 주는 프로그램을 컴퓨터과학과에 요청했다. 학교가 요청한 프로그램을 작성해 보자.

첫 줄에 연세대학교 건물의 수 $N$과 지금까지 디자이너가 요청한 계획의 수 $D$가 주어진다. ($1 \le N \le 200{,}000$, $0 \le D \le 200{,}000$)

건물의 번호는 1번부터 시작한다.

이어 $N$개의 줄에 각 건물에 은행나무를 심을 때의 비용 $G_i$와 플라타너스를 심을 때의 비용 $P_i$가 1번 건물부터 순서대로 주어진다. ($1 \le G_i, P_i \le 10^9$)

이어 $D$개의 줄에 디자이너의 요청 $D$개가 C i j 형태로 주어진다. ($C$는 0 또는 1, $1 \le i \le N$, $1 \le j \le N$, $i \ne j$)

$C$가 0이면 건물 $i$와 건물 $j$에 반드시 같은 종류의 나무를 심어야 한다는 뜻이고, $C$가 1이면 건물 $i$와 건물 $j$에 반드시 다른 종류의 나무를 심어야 한다는 뜻이다.

다음 줄에 추가로 들어오는 디자이너의 요청과 비용 변동을 합한 횟수 $Q$가 주어진다. ($1 \le Q \le 200{,}000$)

이어 $Q$개의 줄에 각 요청과 변동이 C A B 형태로 주어진다. 각 줄은 다음과 같이 구분된다.

1. $C = 0$이면 $1 \le A, B \le N$, $A \ne B$이고, 건물 $A$와 건물 $B$에 같은 종류의 나무를 심어야 한다는 요청이다.
2. $C = 1$이면 $1 \le A, B \le N$, $A \ne B$이고, 건물 $A$와 건물 $B$에 다른 종류의 나무를 심어야 한다는 요청이다.
3. $C = 2$이면 $1 \le A \le N$, $1 \le B \le 10^9$이고, 건물 $A$에 은행나무를 심는 비용이 $B$로 바뀌었다는 뜻이다.
4. $C = 3$이면 $1 \le A \le N$, $1 \le B \le 10^9$이고, 건물 $A$에 플라타너스를 심는 비용이 $B$로 바뀌었다는 뜻이다.

디자이너의 서로 다른 두 요청 $i$와 $j$에 대해, $(A_i, B_i)$와 $(A_j, B_j)$가 일치하거나 $(A_i, B_i)$와 $(B_j, A_j)$가 일치하는 경우는 없다.

모든 요청과 변동은 누적된다.

출력은 총 $Q + 1$개의 줄로 이루어진다.

첫 줄에는 추가적인 요청과 비용 변동이 일어나기 전, 앞서 주어진 $D$개의 요청만 반영했을 때 모든 건물 앞에 나무를 한 그루씩 심는 최소 비용을 출력한다.

이어 $Q$개의 줄에 각 요청과 변동을 반영한 직후에 모든 건물 앞에 나무를 한 그루씩 심는 최소 비용을 출력한다.

주어진 $D$개의 요청과 이어지는 요청을 모두 처리하는 과정에서, 모든 건물 앞에 나무를 한 그루씩 심는 것이 불가능해지는 경우는 없다.

예제에서 연세대학교에는 건물이 4개 있고, 디자이너는 우선 1번과 3번 건물 앞에 같은 나무를 심을 것을 요청했다. 이때 최적은 1번 건물부터 순서대로 은행나무, 플라타너스, 은행나무, 은행나무를 심는 것이며 비용은 17이다.

이어지는 세 가지 변동은 다음과 같다. 1번과 2번 건물 앞에 같은 나무를 심으라는 요청을 받은 뒤에는 모든 건물 앞에 은행나무를 심는 것이 최적이 되고, 비용은 18이다. 1번과 4번 건물 앞에 다른 나무를 심어야 한다는 요청을 받은 뒤에는 플라타너스, 플라타너스, 플라타너스, 은행나무를 심는 것이 최적이고, 비용은 30이다. 마지막으로 4번 건물에 플라타너스를 심는 비용이 100에서 1로 바뀌면서, 최적의 계획은 은행나무, 은행나무, 은행나무, 플라타너스를 심는 것이 되고 비용은 18이다.