Берляндия — государство из $$$n$$$ городов, некоторые из которых соединены $$$n-1$$$ дорогами, при чем от каждого можно добраться до каждого используя имеющиеся дороги. Для каждой дороги так же известно время проезда по ней на автомобиле.
Власти Берляндии посчитали минимальное время, за которое можно добраться от одного города до другого, по всем парам городов и ужаснулись, насколько их дороги устарели. Пора проводить инновации, а именно, $$$m$$$ раз власти выбирают два города $$$u, v$$$ и заменяют дороги на кратчайшем пути из $$$u$$$ в $$$v$$$ на инновационные. Если старое время проезда по дороге было равно $$$w$$$, то после замены дороги время проезда по ней будет равно $$$\lfloor \sqrt{w} \rfloor$$$. После того, как какой-то путь стал инновационным, он может стать еще более инновационным. Другими словами, одна дорога может обновляться несколько раз.
К сожалению, производить ремонт придется вам, работяги. Вычислите сумму кратчайших расстояний по всем парам городов до начала инноваций и после каждого ремонта пути. Так как сумма может быть большая, выведите ее по модулю $$$10^9 + 7$$$.
В первой строке входного файла содержатся два целых числа $$$n, m$$$ — количество городов и запросов, соответственно.
В следующей $$$n-1$$$-й строке содержатся по три целых числа $$$u, v, w$$$ — номера городов соединенных дорогой и время проезда по дороге на автомобиле.
В следующих $$$m$$$ строках содержатся по два целых числа $$$u, v$$$ — номера городов, на пути между которыми производится замена дорог.
$$$$$$1 \le n, m \le 2\cdot10^5$$$$$$ $$$$$$1 \le u, v \le n, 1 \le w \le 10^6$$$$$$
Выведите $$$m+1$$$ строку, каждая из которых содержит по одному целому числу — остаток от деления на $$$10^9 + 7$$$ исходной суммы и $$$m$$$ ответов на запросы.
5 3 1 2 4 2 3 4 1 4 9 1 5 16 1 5 1 3 1 4
140 92 72 48
