На постер во кабинетот по информатика има нацртано едно големо дрво со N темиња и нели N-1 ребро. За секое ребро е означена неговата тежина.

Откако 4 часа ќе решаваат задачи, Иван и Мартин имаат обичај да го симнат постерот на земја, да земат по една фигура во рака, и да започнат со двобој. Двобојот се состои од Q рунди, секоја парна рунда ја игра Мартин, а секоја непарна рунда ја игра Иван.

За секоја рунда се знаат три броеви V, U и K. Играчот (кој ја игра таа рунда) треба да го помине патот во дрвото меѓу темињата V и U. Тој може да избере во кое теме, дали во V, или во U, ќе ја стави својата фигура на почетокот на рундата.
1) Ако фигурата е поставена во темето V, тогаш играчот во таа рунда може да одбере едно ребро и неговата тежина (само за таа рунда) да ја помножи со коефициент -K.
2) Ако фигурата е поставена во темето U, тогаш играчот во таа рунда може да одбере едно ребро и неговата тежина (само за таа рунда) да ја помножи со коефициент K.

Потоа, тој ја движи фигурата од избраното (почетно) теме кон другото (крајно) теме, и ги собира тежините на сите поминати ребра по патот, т.е. играчот во таа рунда ќе добие онолку поени колку што е збирот на ребрата на единствениот пат од V до U, или од U до V. Играчите се одлични и тие секогаш ги освојуваат максималните можни поени за рундата.

Поените од секоја рунда се собираат. Ваша задача е да го отпечатите името на победникот по Q-те рунди и за колку поени победил.

Влез

Првата линија се состои од два цели броја: N (1 ≤ N ≤ 30 000) и Q (1 ≤ Q ≤ 30 000), бројот на темиња во дрвото и бројот на рунди, соодветно.
Следните N-1 линии ќе имаат три цели броеви: A (1 ≤ A ≤ N), B (1 ≤ B ≤ N) и W ( |W| ≤ 100 000), кои означуваат дека постои ребро што ги поврзува темињата A и B, со тежина W.
Следните Q линии ќе имаат три цели броеви: U (1 ≤ U ≤ N), V (1 ≤ V ≤ N) и K (1 ≤ K ≤ 100), темињата и коефициентот во Q-тата рунда, соодветно.

За тест примери кои носат 20% од поените ќе важи: 1 ≤ N, Q ≤ 1 000.
За други тест примери кои носат 30% од поените ќе важи: 1 ≤ N, Q ≤ 30 000 и дрвото е права линија.
За други тест примери кои носат 20% од поените ќе важи: 1 ≤ N, Q ≤ 30 000 и тежините на ребрата се 1 или -1.

Излез

Доколку двобојот на Иван и Мартин е нерешен, отпечатете “=”, во спротивно отпечатете го името на победникот (“Ivan” или “Martin”) и колкава е разликата во добиените поени.

Ограничувања

Временско ограничување: 150 milliseconds
Мемориско ограничување: 64 megabytes

Примери

влез
5 3
2 5 -1
3 1 2
1 5 -3
4 5 2
5 1 46
2 3 62
2 1 43

излез
Ivan 79