Danger#6455
You are given an undirected tree consisting of nodes with weights assigned to edges. You need to perform queries of two types:
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 queries of this type in the input.
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.
The first line contains two integers and (1 \leq n \leq 1000, 0 \leq q \leq 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: -th of these lines contains three integers v_i, u_i and w_i (1 \leq v_i, u_i \leq n, 1 \leq w_i \leq 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 lines contain the description of queries. On each of these lines, the first integer t_i is the type of the query (1 \leq t_i \leq 2). If t_i = 1, it is followed by three integers v_i, u_i and a_i (1 \leq v_i, u_i \leq n, 1 \leq a_i \leq 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 \leq v_i \leq n, 1 \leq k_i \leq 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 from node v_i. It is guaranteed that the number of queries of the first type will not be greater than .
For each query of the second type, print exactly one integer on a separate line: the answer to the query.
Example 1