Ніколи не чекай на гантелі
У лабораторії асистент на ім'я Натан Вада вимірює різницю у вазі між парами зразків. Він використовує ваги, оскільки вони можуть точніше визначити різницю у вазі між двома зразками, коли їхні ваги майже однакові, ніж пружинні ваги.
Час від часу його запитують про різницю у вазі між певними парами зразків. Він може відповісти на ці запити, якщо вже має відповідні результати вимірювань.
Оскільки обсяг даних вимірювань значно зріс, Натан вже не може швидко визначити різницю у вазі. Він просить вас створити програму, яка буде записувати результати вимірювань і автоматично повідомляти різницю у вазі.
Вхідні дані
Вхідні дані складаються з кількох наборів. Перший рядок кожного набору містить два цілі числа 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 у новому рядку.