There are n cities numbered from 1 to n in Berland. Some of them are connected by two-way roads. Each road has its own length — an integer number from 1 to 1000. It is known that from each city it is possible to get to any other city by existing roads. Also for each pair of cities it is known the shortest distance between them. Berland Government plans to build k new roads. For each of the planned road it is known its length, and what cities it will connect. To control the correctness of the construction of new roads, after the opening of another road Berland government wants to check the sum of the shortest distances between all pairs of cities. Help them — for a given matrix of shortest distances on the old roads and plans of all new roads, find out how the sum of the shortest distances between all pairs of cities changes after construction of each road.

Input

The first line contains integer n (2 ≤ n ≤ 300) — amount of cities in Berland. Then there follow n lines with n integer numbers each — the matrix of shortest distances. j-th integer in the i-th row — di, j, the shortest distance between cities i and j. It is guaranteed that di, i = 0, di, j = dj, i, and a given matrix is a matrix of shortest distances for some set of two-way roads with integer lengths from 1 to 1000, such that from each city it is possible to get to any other city using these roads.

Next line contains integer k (1 ≤ k ≤ 300) — amount of planned roads. Following k lines contain the description of the planned roads. Each road is described by three space-separated integers ai, bi, ci (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ ci ≤ 1000) — ai and bi — pair of cities, which the road connects, ci — the length of the road. It can be several roads between a pair of cities, but no road connects the city with itself.

Output

Output k space-separated integers qi (1 ≤ i ≤ k). qi should be equal to the sum of shortest distances between all pairs of cities after the construction of roads with indexes from 1 to i. Roads are numbered from 1 in the input order. Each pair of cities should be taken into account in the sum exactly once, i. e. we count unordered pairs.

Examples

Input

2
0 5
5 0
1
1 2 3


Output

3 

Input

3
0 4 5
4 0 9
5 9 0
2
2 3 8
1 2 1


Output

17 12

Difficulty: HARD
Tags: Graph algorithms

Shortest paths

Starter code:

Solutions:
n = int(input())
mat = []
for _ in range(n):
	mat.append(list(map(int, input().split())))
q = int(input())
ans = []
for _ in range(q):
	(x, y, w) = map(int, input().split())
	x -= 1
	y -= 1
	mat[x][y] = mat[y][x] = min(mat[x][y], w)
	sum1 = 0
	for i in range(n):
		for j in range(n):
			a = mat[i][y] + mat[x][y] + mat[x][j]
			b = mat[i][x] + mat[x][y] + mat[y][j]
			c = mat[i][j]
			mat[i][j] = min(a, b, c)
		sum1 += sum(mat[i])
	ans.append(sum1 // 2)
print(*ans)


N = int(input())
grid = []
for n in range(N):
	grid.append(list(map(int, input().split())))
K = int(input())
ret = []
for k in range(K):
	(A, B, C) = map(int, input().split())
	ans = 0
	A -= 1
	B -= 1
	grid[A][B] = grid[B][A] = min(C, grid[A][B])
	for i in range(N):
		for j in range(N):
			a = grid[i][j]
			b = grid[i][A] + grid[A][B] + grid[B][j]
			c = grid[i][B] + grid[B][A] + grid[A][j]
			grid[i][j] = min(a, b, c)
		ans += sum(grid[i])
	ret.append(ans // 2)
print(*ret)


n = int(input())
a = []
for i in range(n):
	a.append(list(map(int, input().split())))
k = int(input())
for y in range(k):
	(u, v, d) = map(int, input().split())
	u = u - 1
	v = v - 1
	a[u][v] = min(a[u][v], d)
	for i in range(n):
		for j in range(n):
			s = a[i][u] + a[u][v] + a[v][j]
			s2 = a[i][v] + a[u][v] + a[u][j]
			s1 = a[i][j]
			a[i][j] = min(s, s1, s2)
	sum1 = 0
	for i in range(n):
		sum1 += sum(a[i])
	print(sum1 // 2, end=' ')


from sys import stdin, stdout
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def iinp():
	return int(inp())

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

def mp():
	return map(int, inp().split())

def smp():
	return map(str, inp().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(m, val) for j in range(n)]

def remadd(x, y):
	return 1 if x % y else 0

def ceil(a, b):
	return (a + b - 1) // b

def isprime(x):
	if x <= 1:
		return False
	if x in (2, 3):
		return True
	if x % 2 == 0:
		return False
	for i in range(3, int(sqrt(x)) + 1, 2):
		if x % i == 0:
			return False
	return True
n = iinp()
dist = [lmp() for i in range(n)]
k = iinp()
quer = []
for i in range(k):
	(a, b, c) = mp()
	quer.append((a, b, c))
for q in quer:
	(x, y, d) = q
	s = 0
	for i in range(n):
		for j in range(i, n):
			p = min(dist[i][j], dist[i][x - 1] + d + dist[y - 1][j], dist[i][y - 1] + d + dist[x - 1][j])
			dist[i][j] = p
			dist[j][i] = p
			s += dist[i][j]
	print(s, end=' ')
print()


n = int(input())
mt = [[] for _i in range(n)]
for i in range(n):
	mt[i] = list(map(int, input().split()))
kk = int(input())
for i in range(kk):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	if mt[a][b] > c:
		mt[a][b] = c
		mt[b][a] = c
	for i in range(n):
		for j in range(n):
			mt[i][j] = min(mt[i][j], mt[i][a] + mt[b][j] + c, mt[i][b] + mt[a][j] + c)
	ans = 0
	for i in range(n):
		ans += sum(mt[i])
	print(ans // 2)


from sys import stdin
input = stdin.readline
n = int(input())
m = []
for ni in range(n):
	m.append([int(x) for x in input().strip().split()])
q = int(input())
ans = []
for qi in range(q):
	(s, e, v) = [int(x) for x in input().strip().split()]
	s -= 1
	e -= 1
	for i in range(n):
		for j in range(n):
			nd = m[i][s] + v + m[e][j]
			if nd < m[i][j]:
				m[i][j] = nd
				m[j][i] = nd
	td = 0
	for i in range(n):
		for j in range(i + 1, n):
			td += m[i][j]
	ans.append(td)
print(*ans)


from collections import defaultdict

def summ(x):
	s = 0
	for i in range(n):
		for j in range(i + 1, n):
			s += x[i][j]
	return s
INF = 10 ** 15
n = int(input())
dis = []
for _ in range(1, n + 1):
	dis.append(list(map(int, input().split())))
insum = summ(dis)
k = int(input())
for i in range(k):
	(a, b, cost) = list(map(int, input().split()))
	if cost > dis[a - 1][b - 1]:
		print(insum, end=' ')
	else:
		insum = insum + cost - dis[a - 1][b - 1]
		dis[a - 1][b - 1] = cost
		dis[b - 1][a - 1] = cost
		for o in range(n):
			for p in range(o + 1, n):
				if dis[o][p] > dis[o][a - 1] + dis[a - 1][b - 1] + dis[b - 1][p]:
					insum = insum + (dis[o][a - 1] + dis[a - 1][b - 1] + dis[b - 1][p]) - dis[o][p]
					dis[o][p] = dis[o][a - 1] + dis[a - 1][b - 1] + dis[b - 1][p]
					dis[p][o] = dis[o][p]
				if dis[o][p] > dis[o][b - 1] + dis[a - 1][b - 1] + dis[a - 1][p]:
					insum = insum + (dis[o][b - 1] + dis[a - 1][b - 1] + dis[a - 1][p]) - dis[o][p]
					dis[o][p] = dis[o][b - 1] + dis[a - 1][b - 1] + dis[a - 1][p]
					dis[p][o] = dis[o][p]
		print(insum, end=' ')