Никогда не жди гантелей
В лаборатории ассистент по имени Натан Вада измеряет разницу в весе между парами образцов. Он использует весы, так как они позволяют более точно определить разницу в весе между двумя образцами, особенно когда их веса почти одинаковы.
Иногда его просят сообщить разницу в весе между парами образцов. Он может ответить на этот вопрос, если у него уже есть соответствующие результаты измерений.
Поскольку объем данных измерений становится огромным, Натану трудно быстро определить разницу в весе. Он просит вас создать программу, которая будет записывать результаты измерений и автоматически сообщать разницу в весе.
Входные данные
Входные данные состоят из нескольких наборов. Первая строка каждого набора содержит два целых числа N и M. N обозначает количество образцов (2 ≤ N ≤ 100000). Каждому образцу присваивается уникальный номер от 1 до N. Остальная часть набора данных состоит из M строк (1 ≤ M ≤ 100000), каждая из которых представляет собой либо результат измерения, либо запрос. Они даны в хронологическом порядке.
Результат измерения записывается в формате:
! a b w
где образец под номером b тяжелее образца под номером a на w микрограммов (a ≠ b). Это означает, что w=w_b-w_a, где w_a и w_b — веса образцов a и b соответственно. Здесь w — неотрицательное целое число, не превышающее 1000000.
Вы можете быть уверены, что все измерения точны и согласованы.
Запрос записывается в формате:
? a b
и спрашивает разницу в весе между образцами под номерами a и b (a ≠ b).
Последний набор данных заканчивается строкой, содержащей два нуля, разделенные пробелом.
Выходные данные
Для каждого запроса ? a b выведите разницу в весе в микрограммах между образцами под номерами a и b, w_b-w_a, на новой строке, если разница может быть вычислена на основе результатов измерений, полученных до запроса. Разница может быть нулевой, отрицательной или положительной. Вы можете быть уверены, что ее абсолютное значение не превышает 1000000. Если разницу нельзя вычислить на основе результатов измерений, полученных до запроса, выведите UNKNOWN на новой строке.