Danger

You are given an undirected tree consisting of n nodes with weights assigned to edges. You need to perform queries of two types:

1. Add a given value a[i] to all edges on the path from node v[i] to node u[i]. There will be no more than 500 queries of this type in the input.

2. Compute the sum of weights of all edges for which both endpoints are at distance no more than k[i] from node v[i]. The distance between two nodes is the number of edges on the path between them.

You should perform these queries in the given order and for each query of second type, print the computed value.

Input

The first line contains two integers n and q (1 ≤ n ≤ 1000, 0 ≤ q ≤ 500000) which are the number of nodes in the tree and the number of queries, respectively. The next n - 1 lines contain the description of the tree: i-thof these lines contains three integers v[i], u[i] and w[i] (1 ≤ v[i], u[i] ≤ n, 1 ≤ w[i] ≤ 100000) which are the number of nodes this edge connects and its weight, respectively. It is guaranteed that the given graph is a tree.

The following q lines contain the description of queries. On each of these lines, the first integer t[i] is the type of the query (1 ≤ t[i] ≤ 2). If t[i] = 1, it is followed by three integers v[i], u[i] and a[i] (1 ≤ v[i], u[i] ≤ n, 1 ≤ a[i] ≤ 100000) and means you need to add a[i] to all edges on the path from v[i] to u[i]. If t[i] = 2, it is followed by two integers v[i] and k[i] (1 ≤ v[i] ≤ n, 1 ≤ k[i] ≤ n) and means you need to find the sum of weights of all edges for which both endpoints are at distance at most k[i] form node v[i]. It is guaranteed that the number of queries of the first type will not be greater than 500.

Output

For each query of the second type, print exactly one integer on a separate line: the answer to the query.

Examples