Heç vaxt ağırlıqları gözləmə
Laboratoriyada köməkçi Nathan Wada nümunə parçalarının çəkilərini cüt-cüt ölçür. O, tərəzi istifadə edir, çünki nümunələrin çəkiləri demək olar ki, eyni olduqda, tərəzi iki nümunə arasındakı çəki fərqini yaylı tərəzidən daha dəqiq ölçə bilir.
Bəzən o, nümunə cütləri arasındakı çəki fərqlərini soruşur. O, artıq əldə edilmiş ölçmə nəticələrinə əsasən bu fərqləri hesablaya bilər və ya bilməz.
Çünki o, böyük miqdarda ölçmə məlumatı toplayır, artıq çəki fərqlərini dərhal demək asan deyil. Nathan sizdən ölçmə nəticələrini qeyd edən və avtomatik olaraq çəki fərqlərini bildirən bir proqram hazırlamağı xahiş edir.
Giriş verilənləri
Giriş bir neçə datasetdən ibarətdir. Datasetin ilk sətri iki tam ədəd N və M ehtiva edir. N nümunə parçalarının sayını göstərir (2 ≤ N ≤ 100000). Hər bir nümunəyə 1-dən N-ə qədər unikal bir nömrə təyin edilir. Datasetin qalan hissəsi xronoloji ardıcıllıqla verilmiş M sətirdən ibarətdir (1 ≤ M ≤ 100000), hər biri ya ölçmə nəticəsinə, ya da sorğuya uyğundur.
Ölçmə nəticəsi formatda olur,
! a b w
bu, b nömrəli nümunə parçasının a nömrəli nümunə parçasından w mikroqram daha ağır olduğunu göstərir (a ≠ b). Yəni, w=w_b-w_a, burada w_a və w_b müvafiq olaraq a və b nümunələrinin çəkiləridir. Burada w 1000000-i keçməyən qeyri-mənfi tam ədəddir.
Bütün ölçmələrin dəqiq və ardıcıl olduğunu qəbul edə bilərsiniz.
Sorğu formatda olur,
? a b
bu, a və b nömrəli nümunə parçaları arasındakı çəki fərqini soruşur (a ≠ b).
Son dataset bir boşluqla ayrılmış iki sıfırdan ibarət bir sətirlə tamamlanır.
Çıxış verilənləri
Hər bir ? a b sorğusu üçün, əgər sorğudan əvvəlki ölçmə nəticələrinə əsasən çəki fərqi hesablana bilirsə, a və b nömrəli nümunə parçaları arasındakı çəki fərqini mikroqramla, w_b-w_a, yeni sətirlə çap edin. Fərq sıfır, mənfi və ya müsbət ola bilər. Onun mütləq dəyərinin ən çox 1000000 olduğunu qəbul edə bilərsiniz. Əgər sorğudan əvvəlki ölçmə nəticələrinə əsasən fərq hesablana bilmirsə, yeni sətirlə UNKNOWN çap edin.