무빙맨

세로 $N$칸, 가로 $K$칸 크기의 직사각형 격자에 사람들이 살고 있다. 위에서부터 $i$번째, 왼쪽에서부터 $j$번째 격자의 위치를 $(i, j)$라고 하자. ($1 \le i \le N; 1 \le j \le K$) 이 격자에는 $N$명의 사람들이 살고 있는데, 그중 $k$번째 사람은 $(k, 1)$ 위치의 격자에 살고 있다.

각 격자에서는 그 격자에 인접한 아래쪽 격자로 가중치가 있는 단방향 도로가 연결되어 있다. 모든 $i$, $j$에 대해 $(i, j)$에서 $(i+1, j)$로 $C\_{i, j}$의 비용으로 이동할 수 있다. ($1 \le i \le N-1; 1 \le j \le K$) 모든 사람들은 모임을 위해 매달 단방향 도로를 통해 가장 아래쪽 행에 있는 격자로 이동한다.(단, $k$번째 사람은 매달 이동하기 전에 $(k, 1)$에 위치한다.)

악랄한 마법사 피클은, 사람들을 괴롭히기 위해 마법을 부려 마을의 구조를 변형시켰다. 피클은 길이가 $N-1$인 두 배열 $A$, $B$를 정해 $(i, A\_i)$에서 $(i+1, A\_i)$로 이동할 수 있는 도로를 없애고 $(i, A\_i)$에서 $(i+1, B\_i)$로 이동할 수 있는 비용 $C\_{i, A\_i}$의 도로를 만들었다. ($1 \le i \le N-1$) 그럼에도 불구하고 불쌍한 사람들은 한 달에 한 번씩 단방향 도로를 통해 가장 아래쪽 격자로 이동한다.

변덕스러운 피클은 매달 한 번씩 사람들이 이동하기 전에 $i$를 하나 골라 $A\_i$와 $B\_i$의 값을 각각 다른 값으로 바꿔버린다. ($1 \le i \le N-1$)

이제 마법사 피클이 $A\_i$, $B\_i$를 바꿀 때마다, 사람들이 가장 아래쪽 격자로 이동할 때 필요한 비용의 합을 구하시오.

첫 번째 줄에 $N$, $K$가 공백으로 구분되어 주어진다.

두 번째 줄부터 $N-1$개 줄 중 $i$번째 줄에 $C\_{i, 1}, \ldots , C\_{i, K}$가 공백으로 구분되어 주어진다.

그다음 줄부터 $N-1$개의 줄 중 $i$번째 줄에 $A\_i$와 $B\_i$가 공백으로 구분되어 주어진다.

그다음 줄에 피클이 $A\_i$, $B\_i$를 바꾸는 횟수를 나타내는 정수 $Q$가 주어진다.

그다음 줄부터 $Q$개의 줄 중 $i$번째 줄에 세 정수 $k$, $a$, $b$가 공백으로 구분되어 주어진다. 이는 피클이 $A\_k$를 $a$로, $B\_k$를 $b$로 바꾸었음을 의미한다.

$Q$개의 줄에 걸쳐, $i$번째 줄에 $i$번째로 피클이 $A\_k$, $B\_k$를 바꿨을 때 모든 사람들이 가장 아래쪽 행의 격자로 이동할 때 필요한 비용의 합을 출력한다.

• $2 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $1 \le K \le 10$
• $1 \le A\_i, B\_i \le K$ ($1 \le i \le N-1$)
• $1 \le C\_{i, j} \le 10^6$ ($1 \le i \le N-1$; $1 \le j \le K$)
• 모든 쿼리에서 $1 \le k \le N-1$; $1 \le a, b \le K$