Небезпека

У вас є неорієнтоване дерево з 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.

Вихідні дані

Для кожного запиту другого типу виведіть в окремому рядку відповідь на нього.

Приклади