Опасность

Задано неориентированное дерево с n вершинами, ребрам которого присвоены веса. Необходимо выполнить запросы двух типов:

1. Прибавить значение a[i] ко всем ребрам на пути от вершины v[i] до вершины u[i]. Этого типа имеется не более 500 запросов.

2. Вычислить сумму весов всех ребер, оба конца которых находятся на расстоянии не более k[i] от v[i]. Расстояние между двумя вершинами равно числу ребер на пути между ними.

Выполнять запросы следует в указанном порядке. Для каждого запроса второго типа вывести найденное значение.

Входные данные

Первая строка содержит два числа n и q (1 ≤ n ≤ 1000, 0 ≤ q ≤ 500000) - количество вершин в дереве и количество запросов. Следующая n - 1 строка содержит описание дерева: i-ая строка содержит три числа v[i], u[i] и w[i] (1 ≤ v[i], u[i] ≤ n, 1 ≤ w[i] ≤ 100000) - номера вершин, соединенных ребром, и его вес. Гарантируется, что граф является деревом.

Следующие q строк описывают запросы. В этих строках первым числом t[i] является тип запроса (1 ≤ t[i] ≤ 2). Если t[i] = 1, то далее следуют три числа v[i], u[i] и a[i] (1 ≤ v[i], u[i] ≤ n, 1 ≤ a[i] ≤ 100000), означающих что надо добавить a[i] ко всем ребрам на пути от v[i] до u[i]. Если t[i] = 2, то далее следуют два числа v[i] и k[i] (1 ≤ v[i] ≤ n, 1 ≤ k[i] ≤ n), означающих что надо найти сумму весов всех ребер, концы которых находятся на расстоянии не больше k[i] от вершины v[i]. Гарантируется, что запросов первого типа не более 500.

Выходные данные

Для каждого запроса второго типа вывести в отдельной строке ответ на него.

Примеры