15674번 - 가로수

연세대학교에서는 이번에 대대적인 가로수 심기 작업을 한다. 원활한 작업을 위해 학교에서는 어느 정도의 예산이 필요할지 알아보려 한다.

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

학교 측에서는 미리 각 건물 앞에 은행나무를 심을 때의 비용과 플라타너스를 심을 때의 비용을 각각 모두 조사해 두었다. 각 건물이 있는 장소의 지형이나 환경이 다르기 때문에, 같은 나무를 심더라도 다른 건물 앞이라면 비용이 다를 수 있다.

학교 측에서는 최소 비용으로 가로수를 모든 건물 앞에 심을 계획을 작성했다. 하지만, 늦게 프로젝트에 합류한 디자이너는 이대로 가로수를 심을 경우 미관상 좋지 않다는 이야기를 하며, 계획을 꽤 많이 수정해야 한다고 했다. 디자이너의 요청은 두 가지 종류 중 하나였다.

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

설상가상으로, 디자이너의 요청을 받아 계획을 수정하는 일이 오래 걸리자, 미리 조사해 둔 비용들마저 변하기 시작했다. 각 비용은 아래와 같이 두 가지 종류 중 하나로 변한다.

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

학교 측에서는 더이상 손수 계획을 수정하는 것은 무리라고 판단했으며, 이에 컴퓨터과학과 측에 지속적으로 변동하는 계획과 가격을 실시간으로 반영해 최적의 계획을 찾아 주는 프로그램 작성을 요청했다.

학교 측에서 요청한 프로그램을 작성해보도록 하자.

첫 줄에 연세대학교 건물의 수 N, 현재까지 디자이너가 요청한 계획의 수 D가 주어진다. (1 ≤ N ≤ 200,000, 0 ≤ D ≤ 200,000)

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

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

이어 D줄에 걸쳐, 디자이너의 요청 D개가 C i j의 형태로 주어진다. (C = 0 또는 1, 1 ≤ i ≤ N, 1 ≤ j ≤ N, i ≠ j)

C가 0일 경우, 건물 i와 건물 j에는 반드시 같은 나무를 심어야 함을 의미하며, C가 1일 경우엔 건물 i와 건물 j에는 다른 나무를 심어야 함을 의미한다.

다음 줄엔 추가적인 디자이너의 요청과 비용이 변동되는 횟수의 합 Q가 주어진다. (1 ≤ Q ≤ 200,000 )

이어 Q줄에 걸쳐, 각 요청/변동 사항이 C A B의 형태로 주어진다.

각 요청/변동 사항은 아래와 같이 분류된다.

• C=0일 경우, 1 ≤ A, B ≤ N, A ≠ B. 건물 A와 B에는 동일한 나무를 심어야 한다는 요청이다.
• C=1일 경우, 1 ≤ A, B ≤ N, A ≠ B. 건물 A와 B에는 다른 나무를 심어야 한다는 요청이다.
• C=2일 경우, 1 ≤ A ≤ N, 1 ≤ B ≤ 10⁹. 건물 A에 은행나무를 심는 비용이 B로 변했다는 의미이다.
• C=3일 경우, 1 ≤ A ≤ N, 1 ≤ B ≤ 10⁹. 건물 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)