$N \times 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$) 모든 사람들은 모임을 위해 한 달에 한 번씩 단방향 도로를 통해 가장 아래쪽 열에 있는 격자로 이동한다.

그런데, 악랄한 마법사 피클은 사람들을 괴롭히기 위해 마법을 부려 마을의 구조를 변형시켰다. 피클은 크기가 각각 $N-1$인 배열 $A$, $B$를 정해 $(i, A_i)$에서 $(i+1, A_i)$로 이동할 수 있는 도로를 없애고, $(i, A_i)$에서 $(i+1, B_i)$로 이동할 수 있는 도로를 만들었다.($1 \le i \le N-1$) 만들어진 도로의 가중치는 제거된 도로의 가중치와 같다. 그럼에도 불구하고 불쌍한 사람들은 한 달에 한 번씩 단방향 도로를 통해 가장 오른쪽 격자로 이동한다.

심지어 피클은 변덕스럽기까지 한데, 피클은 사람들이 이동하기 전에 $i$를 하나 골라 $A_i$와 $B_i$를 바꾸기까지 한다.($1 \le i \le N-1$)

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

Input

첫 줄에 $N$, $K$가 공백을 사이에 두고 주어진다.

둘째 줄부터 $N$번째 줄까지 $(i+1)$번째 줄에는 $C_{i, 1}, \ldots , C_{i, K}$가 공백을 사이에 두고 주어진다.

$N+1$째 줄부터 $2N-1$번째 줄까지 $N-1$개의 줄에 걸쳐 $(i+N)$번째 줄에는 $A_i$와 $B_i$가 공백을 사이에 두고 주어진다.

$2N$번째 줄에는 피클이 $A_i$, $B_i$를 바꾸는 횟수 $Q$가 주어진다.

$2N+1$번째 줄부터 $2N+Q$번째 줄까지 $(i+2N)$번째 줄에는 $k, a, b$가 주어지는데, 이는 피클이 $A_k$를 $a$로, $B_k$를 $b$로 바꾸었음을 의미한다.

($2 \le N \le 2 \times 10^5, 1 \le Q \le 2 \times 10^5, 1 \le K \le 10$, 모든 $i$에 대해 $1 \le A_i, B_i \le K$, 모든 $i, j$에 대해 $1 \le C_{i, j} \le 10^6$, 모든 쿼리에서 $1 \le k \le N-1, 1 \le a, b \le K$)

Output

출력은 총 $Q$줄로 구성된다.

$i$번째 줄에는 $i$번째로 피클이 $A_k$, $B_k$를 바꿨을 때 모든 사람들이 가장 아래쪽 열의 격자로 이동할 때 필요한 비용의 합을 출력한다.

Scoring

1. (5점) $K=1$

2. (10점) $N, Q \le 300$

3. (20점) $N, Q \le 3000$

4. (10점) $Q \le 100$

5. (55점) 추가적인 제약 조건 없음.

Examples

Input 1

6 3
1 100 10000
1 100 10000
1 100 10000
1 100 10000
1 100 10000
3 1
1 2
2 1
1 3
1 1
4
1 2 3
2 3 2
5 1 3
2 1 1

Output 1

40209
40011
40011
40011