Yet Another Maxflow Problem

이 문제에서는 매우 특별한 네트워크를 다루어야 한다.

네트워크는 파트 A와 파트 B의 두 부분으로 구성된다. 각 파트는 n개의 정점으로 구성되며, 파트 A의 i-th 정점은 Ai로, 파트 B의 i-th 정점은 Bi로 나타낸다.

각 인덱스 i (1 ≤ i < n)에 대해, 정점 Ai에서 정점 Ai + 1로 향하는 유향 간선과 Bi에서 Bi + 1로 향하는 유향 간선이 각각 존재한다. 이 간선들의 용량은 입력으로 주어진다. 또한 파트 A에서 파트 B로 향하는 유향 간선이 여러 개 있을 수도 있다(하지만 B에서 A로 향하는 간선은 절대 없다).

이 네트워크에서 A1에서 Bn으로 가는 최대 유량 값을 계산해야 한다. Ai와 Ai + 1을 연결하는 간선들의 용량은 때때로 변경될 수 있으며, 이러한 변경 후에도 최대 유량 값을 유지해야 한다. 그 밖의 네트워크는 고정되어 있다(파트 B에는 변경이 없고, A에서 B로 향하는 간선에도 변경이 없으며, 간선의 추가나 삭제도 없다).

네트워크의 구조를 더 잘 이해하려면 예제와 참고를 살펴보라.

첫째 줄에 세 정수 n, m, q (2 ≤ n, m ≤ 2·105, 0 ≤ q ≤ 2·105)가 주어진다. 각각 각 파트의 정점 수, A에서 B로 향하는 간선 수, 변경 횟수를 나타낸다.

이어서 n - 1개의 줄이 주어진다. i-th 줄에는 두 정수 xi와 yi이 주어지며, 이는 Ai에서 Ai + 1로 향하는 간선의 용량이 xi이고, Bi에서 Bi + 1로 향하는 간선의 용량이 yi임을 나타낸다 (1 ≤ xi, yi ≤ 109).

이어서 A에서 B로 향하는 간선들을 설명하는 m개의 줄이 주어진다. 각 줄에는 세 정수 x, y, z이 주어지며, 용량이 z인 Ax에서 By로 향하는 간선을 나타낸다 (1 ≤ x, y ≤ n, 1 ≤ z ≤ 109). Ax에서 By로 향하는 간선이 여러 개 있을 수도 있다.

그다음 네트워크의 변경 순서를 설명하는 q개의 줄이 주어진다. i-th 줄에는 두 정수 vi와 wi가 주어지며, 이는 Avi에서 Avi + 1로 향하는 간선의 용량이 wi로 설정됨을 나타낸다 (1 ≤ vi < n, 1 ≤ wi ≤ 109).

먼저 원래 네트워크의 최대 유량 값을 출력한다. 그다음 q개의 정수를 출력하며, 그중 i-th 정수는 i-th 변경 후의 최대 유량 값과 같아야 한다.

다음은 예제의 원래 네트워크이다.