8690: BZOJ4690：Never Wait for Weights

在实验室中，Nathan Wada作为助手的职责是测定两个样品的重量差异。当样品的差异很小时，使用天平能比使用 弹簧秤得到更精确的结果，所以他只使用天平来测得一些样品的重量差。他偶尔会被询问一些样品的重量差，而他 能否回答这些问题取决于在回答相应问题时他已经得到的测量结果。由于他所在处理的测量数据是巨大的，所以他 希望你能写个程序帮他处理数据和回答问题。

输入格式

输入包含多组测试数据。每组数据第一行包含两个整数 N 和 M ，其中 N 表示样品的数量， 样品从 1 到 N 标号，满足 2≤N≤100000 。 接下来 M 行，每行包括一个测量结果或者询问，按时间顺序给出，满足 1≤M≤100000 。 一个测量结果被格式化为 ! a b w ，表示第 a 个样品比第 b 个样品轻 w 个单位重量 满足 a≠b,0≤w≤1000000 ，且任意的测试结果互不矛盾。 一个询问被格式化为 ? a b ，表示询问第 a 个样品比第 b 个样品轻多少个单位重量，满足 a≠b 。 输入以两个零作为结束。

输出格式

对于每个询问输出一行，如果能回答问题，则输出问题的答案，你可以认为答案的绝对值不超过 1000000  否则输出 UNKNOWN ，表示不能回答问题。

样例输入

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 

样例输出

1
-1
UNKNOWN
100
200
-50

提示

没有写明提示

题目来源

鸣谢Tangjz提供试题