In a laboratory, an assistant, Nathan Wada, is measuring weight differences between sample pieces pair by pair. He is using a balance because it can more precisely measure the weight difference between two samples than a spring scale when the samples have nearly the same weight.

He is occasionally asked the weight differences between pairs of samples. He can or cannot answer based on measurement results already obtained.

Since he is accumulating a massive amount of measurement data, it is now not easy for him to promptly tell the weight differences. Nathan asks you to develop a program that records measurement results and automatically tells the weight differences.



Input

The input consists of multiple datasets. The first line of a dataset contains two integers N and M. N denotes the number of sample pieces (2 ≤ N ≤ 100,000). Each sample is assigned a unique number from 1 to N as an identifier. The rest of the dataset consists of M lines (1 ≤ M ≤ 100,000), each of which corresponds to either a measurement result or an inquiry. They are given in chronological order.

A measurement result has the format,

! a b w

which represents the sample piece numbered b is heavier than one numbered a by w micrograms (a ≠ b). That is, w = wb − wa, where wa and wb are the weights of a and b, respectively. Here, w is a non-negative integer not exceeding 1,000,000.

You may assume that all measurements are exact and consistent.

An inquiry has the format,

? a b

which asks the weight difference between the sample pieces numbered a and b (a ≠ b).

The last dataset is followed by a line consisting of two zeros separated by a space.

Output

For each inquiry, ? a b, print the weight difference in micrograms between the sample pieces numbered a and b, wb − wa, followed by a newline if the weight difference can be computed based on the measurement results prior to the inquiry. The difference can be zero, or negative as well as positive. You can assume that its absolute value is at most 1,000,000. If the difference cannot be computed based on the measurement results prior to the inquiry, print UNKNOWN followed by a newline.

Example

Input

2 2
! 1 2 1
? 1 2
2 2
! 1 2 1
? 2 1
4 7
! 1 2 100
? 2 3
! 2 3 100
? 2 3
? 1 3
! 4 3 150
? 4 1
0 0


Output

1
-1
UNKNOWN
100
200
-50

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
class Value_UnionFind:

	def __init__(self, n):
		self.par = [i for i in range(n)]
		self.differ_weight = [0] * n
		self.rank = [0] * n

	def root(self, x):
		if x == self.par[x]:
			return x
		r = self.root(self.par[x])
		self.differ_weight[x] += self.differ_weight[self.par[x]]
		self.par[x] = r
		return r

	def weight(self, x):
		self.root(x)
		return self.differ_weight[x]

	def unit(self, x, y, w):
		w += self.weight(x)
		w -= self.weight(y)
		x = self.root(x)
		y = self.root(y)
		if x == y:
			return False
		if self.rank[x] < self.rank[y]:
			(x, y, w) = (y, x, -w)
		if self.rank[x] == self.rank[y]:
			self.rank[x] += 1
		self.par[y] = x
		self.differ_weight[y] = w
		return True

	def differ(self, x, y):
		return self.weight(y) - self.weight(x)

def main(n, m):
	Union = Value_UnionFind(n)
	for _ in range(m):
		x = list(map(str, input().split()))
		q = x[0]
		if q == '!':
			(a, b, w) = map(int, x[1:])
			Union.unit(a - 1, b - 1, w)
		if q == '?':
			(a, b) = map(int, x[1:])
			if Union.root(a - 1) != Union.root(b - 1):
				print('UNKNOWN')
			else:
				print(Union.differ(a - 1, b - 1))
while 1:
	(n, m) = map(int, input().split())
	if n == m == 0:
		break
	main(n, m)


class PotUnionFind:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n
		self.diff_p = [0] * n

	def root(self, x):
		while self.parent[x] != x:
			self.diff_p[x] += self.diff_p[self.parent[x]]
			self.parent[x] = self.parent[self.parent[x]]
			x = self.parent[x]
		return x

	def weight(self, x):
		c = 0
		while self.parent[x] != x:
			self.diff_p[x] += self.diff_p[self.parent[x]]
			self.parent[x] = self.parent[self.parent[x]]
			c += self.diff_p[x]
			x = self.parent[x]
		return c

	def merge(self, x, y, dxy):
		dxy += self.weight(x) - self.weight(y)
		(x, y) = (self.root(x), self.root(y))
		if x == y:
			return False
		if self.size[x] < self.size[y]:
			(x, y, dxy) = (y, x, -dxy)
		self.size[x] += self.size[y]
		self.parent[y] = x
		self.diff_p[y] = dxy
		return True

	def issame(self, x, y):
		return self.root(x) == self.root(y)

	def diff(self, x, y):
		if self.root(x) == self.root(y):
			return self.weight(y) - self.weight(x)
		else:
			return None

	def getsize(self, x):
		return self.size[self.root(x)]
import sys
while True:
	(n, Q) = [int(i) for i in input().split()]
	if n == 0 and Q == 0:
		exit()
	T = PotUnionFind(n)
	for _ in [0] * Q:
		u = [i for i in sys.stdin.readline().split()]
		if u[0] == '!':
			(u1, u2, u3) = (int(u[1]) - 1, int(u[2]) - 1, int(u[3]))
			T.merge(u1, u2, u3)
		else:
			(u1, u2) = (int(u[1]) - 1, int(u[2]) - 1)
			if T.issame(u1, u2):
				print(T.diff(u1, u2))
			else:
				print('UNKNOWN')


def solve():

	def measurement(a, b, w):
		a_root = root[a]
		b_root = root[b]
		if a_root != b_root:
			a_member = member[a_root]
			b_member = member[b_root]
			offset = w - (weight[b] - weight[a])
			if len(a_member) > len(b_member):
				a_member.extend(b_member)
				for n in b_member:
					root[n] = a_root
					weight[n] += offset
			else:
				b_member.extend(a_member)
				for n in a_member:
					root[n] = b_root
					weight[n] -= offset

	def inquiry(a, b):
		if root[a] == root[b]:
			return weight[b] - weight[a]
		else:
			return 'UNKNOWN'

	def operation(line):
		if line[0] == '!':
			(a, b, w) = map(int, line[2:].split())
			measurement(a, b, w)
		else:
			(a, b) = map(int, line[2:].split())
			return inquiry(a, b)
	import sys
	file_input = sys.stdin.readlines()
	while True:
		(N, M) = map(int, file_input[0].split())
		if N == 0:
			break
		root = [i for i in range(N + 1)]
		member = [[i] for i in range(N + 1)]
		weight = [0] * (N + 1)
		ans = (operation(line) for line in file_input[1:M + 1])
		ans = filter(lambda x: x != None, ans)
		print(*ans, sep='\n')
		del file_input[:M + 1]
solve()


class WeightedUnionFind(object):
	__slots__ = ['nodes', 'weight']

	def __init__(self, n: int) -> None:
		self.nodes = [-1] * n
		self.weight = [0] * n

	def get_root(self, x: int) -> int:
		if x < 0:
			raise ValueError('Negative Index')
		if self.nodes[x] < 0:
			return x
		else:
			root = self.get_root(self.nodes[x])
			self.weight[x] += self.weight[self.nodes[x]]
			self.nodes[x] = root
			return root

	def relate(self, smaller: int, bigger: int, diff_weight: int) -> None:
		if smaller < 0 or bigger < 0:
			raise ValueError('Negative Index')
		(root_a, root_b) = (self.get_root(smaller), self.get_root(bigger))
		new_weight = diff_weight + self.weight[smaller] - self.weight[bigger]
		if root_a == root_b:
			if self.weight[smaller] + diff_weight == self.weight[bigger]:
				return
			raise ValueError('relateに矛盾あり')
		if self.nodes[root_a] > self.nodes[root_b]:
			(root_a, root_b, new_weight) = (root_b, root_a, -new_weight)
		self.nodes[root_a] += self.nodes[root_b]
		self.nodes[root_b] = root_a
		self.weight[root_b] = new_weight

	def diff(self, x: int, y: int) -> int:
		(root_x, root_y) = (self.get_root(x), self.get_root(y))
		if root_x != root_y:
			return None
		return self.weight[y] - self.weight[x]
import sys
while True:
	(N, M) = map(int, input().split())
	if N == 0:
		break
	uf = WeightedUnionFind(N + 1)
	for (qtype, a, b, *c) in (sys.stdin.readline().split() for _ in [0] * M):
		if qtype == '!':
			uf.relate(int(a), int(b), int(c[0]))
		else:
			diff = uf.diff(int(a), int(b))
			print(diff if diff is not None else 'UNKNOWN')


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 13
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

class UnionFind:

	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		if self.table[x] < 0:
			return x
		else:
			self.table[x] = self.find(self.table[x])
			return self.table[x]

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] <= self.table[s2]:
				self.table[s1] += self.table[s2]
				self.table[s2] = s1
			else:
				self.table[s2] += self.table[s1]
				self.table[s1] = s2
			return True
		return False

	def subsetall(self):
		a = []
		for i in range(len(self.table)):
			if self.table[i] < 0:
				a.append((i, -self.table[i]))
		return a

def main():
	random.seed(42)
	rr = []

	def f(n, m):
		qa = [LS() for _ in range(m)]
		d = collections.defaultdict(lambda : collections.defaultdict(int))
		for i in range(n + 1):
			d[i][i] = random.randrange(1, 100)
		r = []
		uf = UnionFind(n + 1)
		for q in qa:
			if q[0] == '!':
				(a, b, w) = map(int, q[1:])
				fa = uf.find(a)
				fb = uf.find(b)
				if fa == fb:
					continue
				uf.union(a, b)
				if fa == uf.find(a):
					sa = w + (d[fa][a] - d[fb][b])
					for k in d[fb].keys():
						d[fa][k] = d[fb][k] + sa
				else:
					sa = d[fa][a] - d[fb][b] + w
					for k in d[fa].keys():
						d[fb][k] = d[fa][k] - sa
			else:
				(a, b) = map(int, q[1:])
				fa = uf.find(a)
				if fa != uf.find(b):
					r.append('UNKNOWN')
				else:
					r.append(d[fa][b] - d[fa][a])
		return r
	while 1:
		(n, m) = LI()
		if n == 0 and m == 0:
			break
		rr.extend(f(n, m))
	return '\n'.join(map(str, rr))
print(main())


import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

class WeightedUnionFind:

	def __init__(self, N):
		self.N = N
		self.parents = [-1] * self.N
		self.diff_weight = [0] * self.N

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			p = self.find(self.parents[x])
			self.diff_weight[x] += self.diff_weight[self.parents[x]]
			self.parents[x] = p
			return p

	def weight(self, x):
		self.find(x)
		return self.diff_weight[x]

	def diff(self, x, y):
		if self.find(x) == self.find(y):
			return self.weight(y) - self.weight(x)
		else:
			return 10000000000

	def unite(self, x, y, w):
		w += self.weight(x)
		w -= self.weight(y)
		x = self.find(x)
		y = self.find(y)
		if x == y:
			if self.diff(x, y) == w:
				return True
			else:
				return False
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
			w *= -1
		self.parents[x] += self.parents[y]
		self.parents[y] = x
		self.diff_weight[y] = w
		return True

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def size(self, x):
		return -self.parents[self.find(x)]

def solve(N, M):
	uf = WeightedUnionFind(N)
	for _ in range(M):
		q = input().split()
		if q[0] == '!':
			(a, b, w) = map(int, q[1:])
			a -= 1
			b -= 1
			uf.unite(a, b, w)
		else:
			(a, b) = map(int, q[1:])
			a -= 1
			b -= 1
			ans = uf.diff(a, b)
			if ans == 10000000000:
				print('UNKNOWN')
			else:
				print(ans)

def main():
	while True:
		(N, M) = map(int, input().split())
		if N == 0 and M == 0:
			break
		solve(N, M)
main()


import sys
sys.setrecursionlimit(10 ** 5)

class UnionFind:

	def __init__(self, n):
		self.parents = list(range(n))
		self.weight = [0] * n
		self.rank = [0] * n

	def find(self, a):
		if self.parents[a] == a:
			return a
		p = self.find(self.parents[a])
		self.weight[a] += self.weight[self.parents[a]]
		self.parents[a] = p
		return p

	def union(self, a, b, w):
		(self.find(a), self.find(b))
		w += self.weight[a]
		w -= self.weight[b]
		a = self.find(a)
		b = self.find(b)
		if a == b:
			return
		if self.rank[a] < self.rank[b]:
			self.parents[a] = b
			self.weight[a] = -w
		else:
			self.parents[b] = a
			self.weight[b] = w
			if self.rank[a] == self.rank[b]:
				self.rank[a] += 1

	def weight_check(self, a, b):
		(self.find(a), self.find(b))
		return -self.weight[a] + self.weight[b]
while True:
	(N, M) = map(int, input().split())
	if not N | M:
		break
	uf = UnionFind(N)
	for i in range(M):
		input_str = input().split()
		if input_str[0] == '!':
			(a, b, w) = map(int, input_str[1:])
			uf.union(a - 1, b - 1, w)
		else:
			(a, b) = map(lambda x: int(x) - 1, input_str[1:])
			if uf.find(a) != uf.find(b):
				print('UNKNOWN')
				continue
			print(uf.weight_check(a, b))


import sys
sys.setrecursionlimit(10 ** 6)

def root(x):
	if x == parent[x]:
		return x
	y = root(parent[x])
	relative[x] += relative[parent[x]]
	parent[x] = y
	return y

def unite(a, b, w):
	pa = root(a)
	pb = root(b)
	pw = relative[a] + w - relative[b]
	if pa < pb:
		parent[pb] = pa
		relative[pb] = pw
	else:
		parent[pa] = pb
		relative[pa] = -pw
while 1:
	(N, M) = map(int, input().split())
	if N == M == 0:
		break
	(*parent,) = range(N)
	relative = [0] * N
	for i in range(M):
		cmd = input().split()
		if cmd[0] == '!':
			(a, b, w) = map(int, cmd[1:])
			unite(a - 1, b - 1, w)
		else:
			(a, b) = map(int, cmd[1:])
			if root(a - 1) != root(b - 1):
				print('UNKNOWN')
			else:
				print(relative[b - 1] - relative[a - 1])


import sys
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
ni = lambda : int(ns())
nin = lambda y: [ni() for _ in range(y)]
na = lambda : list(map(int, stdin.readline().split()))
nan = lambda y: [na() for _ in range(y)]
nf = lambda : float(ns())
nfn = lambda y: [nf() for _ in range(y)]
nfa = lambda : list(map(float, stdin.readline().split()))
nfan = lambda y: [nfa() for _ in range(y)]
ns = lambda : stdin.readline().rstrip()
nsn = lambda y: [ns() for _ in range(y)]
ncl = lambda y: [list(ns()) for _ in range(y)]
nas = lambda : stdin.readline().split()

class WUnionFind:

	def __init__(self, n, sum_unity=0):
		self.n = n
		self.par = [i for i in range(n)]
		self.rank = [0 for _ in range(n)]
		self.diff_weight = [sum_unity for _ in range(n)]
		self._size = [1 for _ in range(n)]
		self._edges = 0

	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			r = self.find(self.par[x])
			self.diff_weight[x] += self.diff_weight[self.par[x]]
			self.par[x] = r
			return r

	def unite(self, x, y, w):
		w += self.weight(x)
		w -= self.weight(y)
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.rank[x] < self.rank[y]:
			self.par[x] = y
			self.diff_weight[x] = -w
			self._size[y] += self._size[x]
			self._edges += 1
		else:
			self.par[y] = x
			self.diff_weight[y] = w
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1
			self._size[x] += self._size[y]
			self._edges += 1

	def weight(self, x):
		self.find(x)
		return self.diff_weight[x]

	def diff(self, x, y):
		return self.weight(y) - self.weight(x)

	def size(self, x):
		x = self.find(x)
		return self._size[x]

	def trees(self):
		return self.n - self._edges

	def same(self, x, y):
		return self.find(x) == self.find(y)
while True:
	(n, m) = na()
	if n == 0 and m == 0:
		break
	wuf = WUnionFind(n)
	for i in range(m):
		que = nas()
		if que[0] == '!':
			(a, b, w) = list(map(int, que[1:]))
			a -= 1
			b -= 1
			wuf.unite(a, b, w)
		elif que[0] == '?':
			(a, b) = list(map(int, que[1:]))
			a -= 1
			b -= 1
			if wuf.same(a, b):
				print(wuf.diff(a, b))
			else:
				print('UNKNOWN')


class WeightedUnionFind:

	def __init__(self, n):
		self.par = [i for i in range(n + 1)]
		self.rank = [0] * (n + 1)
		self.weight = [0] * (n + 1)

	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			y = self.find(self.par[x])
			self.weight[x] += self.weight[self.par[x]]
			self.par[x] = y
			return y

	def weighting(self, x):
		self.find(x)
		return self.weight[x]

	def union(self, x, y, w):
		px = self.find(x)
		py = self.find(y)
		if px != py:
			if self.rank[px] < self.rank[py]:
				self.par[px] = py
				self.weight[px] = w - self.weight[x] + self.weight[y]
			else:
				self.par[py] = px
				self.weight[py] = -w - self.weight[y] + self.weight[x]
				if self.rank[px] == self.rank[py]:
					self.rank[px] += 1

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def diff(self, x, y):
		return self.weight[x] - self.weight[y]
(N, M) = (1, 1)
while True:
	(N, M) = map(int, input().split())
	if (N == 0) & (M == 0):
		quit()
	info = [list(input().split()) for i in range(M)]
	wuf = WeightedUnionFind(N)
	for i in range(M):
		if info[i][0] == '!':
			wuf.union(int(info[i][1]), int(info[i][2]), int(info[i][3]))
		elif wuf.same(int(info[i][1]), int(info[i][2])):
			print(wuf.diff(int(info[i][1]), int(info[i][2])))
		else:
			print('UNKNOWN')


def solve():

	def measurement(a, b, w):
		a_root = root[a]
		b_root = root[b]
		if a_root != b_root:
			a_member = member[a_root]
			b_member = member[b_root]
			offset = w - (weight[b] - weight[a])
			if len(a_member) > len(b_member):
				a_member.extend(b_member)
				for n in b_member:
					root[n] = a_root
					weight[n] += offset
			else:
				b_member.extend(a_member)
				for n in a_member:
					root[n] = b_root
					weight[n] -= offset

	def inquiry(a, b):
		if root[a] == root[b]:
			return weight[b] - weight[a]
		else:
			return 'UNKNOWN'
	import sys
	file_input = sys.stdin
	while True:
		(N, M) = map(int, file_input.readline().split())
		if N == 0:
			break
		root = [i for i in range(N + 1)]
		member = [[i] for i in range(N + 1)]
		weight = [0] * (N + 1)
		for _ in range(M):
			line = file_input.readline()
			if line[0] == '!':
				(a, b, w) = map(int, line[2:].split())
				measurement(a, b, w)
			else:
				(a, b) = map(int, line[2:].split())
				print(inquiry(a, b))
solve()


def solve():

	def measurement(a, b, w):
		a_root = root[a]
		b_root = root[b]
		if a_root != b_root:
			a_member = member[a_root]
			b_member = member[b_root]
			offset = w - (weight[b] - weight[a])
			if len(a_member) > len(b_member):
				a_member.extend(b_member)
				for n in b_member:
					root[n] = a_root
					weight[n] += offset
			else:
				b_member.extend(a_member)
				for n in a_member:
					root[n] = b_root
					weight[n] -= offset

	def inquiry(a, b):
		if root[a] == root[b]:
			return weight[b] - weight[a]
		else:
			return 'UNKNOWN'
	import sys
	file_input = sys.stdin.readlines()
	while True:
		(N, M) = map(int, file_input[0].split())
		if N == 0:
			break
		root = [i for i in range(N + 1)]
		member = [[i] for i in range(N + 1)]
		weight = [0] * (N + 1)
		for line in file_input[1:M + 1]:
			if line[0] == '!':
				(a, b, w) = map(int, line[2:].split())
				measurement(a, b, w)
			else:
				(a, b) = map(int, line[2:].split())
				print(inquiry(a, b))
		del file_input[:M + 1]
solve()


def solve():

	def measurement(a, b, w):
		a_root = root[a]
		b_root = root[b]
		if a_root != b_root:
			a_member = member[a_root]
			b_member = member[b_root]
			offset = w - (weight[b] - weight[a])
			if len(a_member) > len(b_member):
				a_member.extend(b_member)
				for n in b_member:
					root[n] = a_root
					weight[n] += offset
			else:
				b_member.extend(a_member)
				for n in a_member:
					root[n] = b_root
					weight[n] -= offset

	def inquiry(a, b):
		if root[a] == root[b]:
			return weight[b] - weight[a]
		else:
			return 'UNKNOWN'
	import sys
	file_input = sys.stdin.readlines()
	ans = []
	while True:
		(N, M) = map(int, file_input[0].split())
		if N == 0:
			break
		root = [i for i in range(N + 1)]
		member = [[i] for i in range(N + 1)]
		weight = [0] * (N + 1)
		for line in file_input[1:M + 1]:
			if line[0] == '!':
				(a, b, w) = map(int, line[2:].split())
				measurement(a, b, w)
			else:
				(a, b) = map(int, line[2:].split())
				ans.append(inquiry(a, b))
		del file_input[:M + 1]
	print(*ans, sep='\n')
solve()