Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTIT133I - Phương pháp cân

Trong phòng thí nghiệm, kĩ sư Tèo đang hoàn thiện chiếc cân thế hệ mới của mình. Với mục đích cân những vật có khối lượng rất nhỏ (cỡ microgram), nên anh ta không sử dụng phương pháp cân trực tiếp mà dùng phương pháp gián tiếp, đó là so sánh sự chênh lệch về khối lượng giữa từng cặp mẫu thử.

Tèo thử nghiệm chiếc cân mới với N mẩu bánh. Tèo thực hiện 1 số lần cân với các mẩu bánh, và từ kết quả đó, anh ta có thể biết được sự chênh lệch khối lượng giữa các mẩu bánh với nhau. Tuy nhiên, anh bạn Tí không tin tưởng vào cỗ máy mới của người bạn mình. Và Tí đã đưa ra thử thách cho chiếc máy mới của Tèo.

Input

Gồm nhiều bộ test.

Mỗi bộ test bắt đầu bởi 2 số N và M. N là số lượng miếng bánh . M là số truy vấn (2 ≤ N, M ≤ 100 000).

M dòng sau, mỗi dòng là một truy vấn. Có 2 loại truy vấn:

* Loại 1: ! a b w (a != b) cho biết miếng bánh b nặng hơn miếng bánh a là w microgram.
Hay là w_b - w_a = w (w < 1 000 000).

* Loại 2: ? a b yêu cầu bạn hãy cho biết sự chênh lệch về khối lượng giữa miếng bánh a và b.

Output

Với mỗi query dạng ? a b, hãy in ra sự khác nhau về khối lượng giữa 2 miếng bánh a,b (w_a - w_b). Đáp số có thể dương, âm, hoặc bằng 0, và có giá trị tuyệt đối luôn nhỏ hơn 1 000 000.

Nếu không thể xác định được sự chênh lệch về khối lượng, in ra UNKNOWN.

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

Được gửi lên bởi:adm
Ngày:2013-02-16
Thời gian chạy:10s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP CPP C++ 4.3.2 CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2015-06-24 16:56:58 Z3r0_L0v3
Chả hiểu mình sai chỗ nào nữa. Thử thấy ổn hết rồi mà -_-
2014-05-14 16:23:10 Black Hole
in ra sự khác nhau về khối lượng giữa 2 miếng bánh a,b. sao lại w_a - w_b nhỉ @@
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.