Skôr než si Miško darčeky rozbalí, snaží sa uhádnuť, v ktorom z nich sa čo skrýva. A pri hádaní mu často pomôže okrem rozmerov darčeka aj jeho váha. Snaží sa preto zistiť, ktorý darček koľko váži. Pomocou dvojramenných váh a pár malých závaží vie Miško porovnať váhu ľubovoľných dvoch darčekov.
Napíšte program, ktorý bude spracúvať postupnosť vážení a odpovedať pomedzi ne Miškovi na otázky.
V prvom riadku vstupu sú dve celé čísla $d$ a $u$: počet darčekov a počet udalostí. Darčeky sú očíslované od $1$ po $n$. Platí $2 \leq d \leq 100~000$ a $1 \leq u \leq 100~000$. Nasleduje $u$ riadkov. Každý z nich popisuje buď nové váženie, alebo otázku. Váženie popisujeme nasledovným riadkom:
! a b w
Tento riadok hovorí, že darček $b$ je o $w$ gramov ťažší ako darček $a$. Môžete predpokladať, že $0 \leq w \leq 1~000~000$. Môžete tiež predpokladať, že všetky merania sú presné a navzájom konzistentné.
Otázku popisujeme nasledovným riadkom:
? a b
Na túto otázku treba odpovedať, o koľko gramov je darček $b$ ťažší ako darček $a$. Občas sa táto odpoveď nemusí dať z dovtedy známych vážení určiť. Môžete predpokladať, že každá odpoveď, ktorá sa určiť dá, bude v absolútnej hodnote nanajvýš rovná $1~000~000$.
Pre každú otázku vypíšte jeden riadok: buď s odpoveďou na ňu, alebo s textom UNKNOWN ak danú odpoveď
z dovtedy uskutočnených vážení určiť nevieme.
2 3
! 1 2 1
? 1 2
? 2 1
1
-1
4 7
! 1 2 100
? 2 3
! 2 3 100
? 2 3
? 1 3
! 4 3 150
? 4 1
UNKNOWN
100
200
-50