Fibonacci Fruit Tree

Wolfycz is fascinated by the Fibonacci sequence. He defines \(Fib_i\) as the \(i\)-th Fibonacci number with \(Fib_0=0,\; Fib_1=1\) and \(Fib_i = Fib_{i-1}+Fib_{i-2}\) for all \(i\geq 2\). One day, he plants a tree (an undirected tree with \(n\) nodes and \(n-1\) edges, with node 1 as the root). Initially, no node bears any funny fruit. To help the tree grow, he uses expensive fertilizer. Each time he applies \(k\) grams of fertilizer on a node \(x\), every node in the subtree of \(x\) (including \(x\) itself) grows some fruits. In particular, if a node in the subtree is at a distance \(D\) from \(x\), it will produce \(Fib_{D+k}\) fruits.

After various fertilizations, Wolfycz sometimes asks for the total number of fruits along the unique path between two nodes \(u\) and \(v\). Your task is to process these operations.

Note: All formulas must be represented in LaTeX format. For example, the Fibonacci relation should appear as \(Fib_i = Fib_{i-1} + Fib_{i-2}\).

inputFormat

The first line contains two integers \(n\) and \(q\) representing the number of nodes in the tree and the number of operations, respectively.

The next \(n-1\) lines each contain two integers \(u\) and \(v\) indicating an edge between nodes \(u\) and \(v\). The tree is rooted at node 1.

The following \(q\) lines describe the operations. Each operation is in one of the following two formats:

• 1 x k: Fertilize node \(x\) with \(k\) grams. This adds \(Fib_{D+k}\) fruits to every node in the subtree of \(x\), where \(D\) is the distance from \(x\) to that node.
• 2 u v: Query the total number of fruits on the unique path between nodes \(u\) and \(v\).

outputFormat

For each query (operation of type 2), output one line containing the total number of fruits on the path between the given nodes.

sample

5 5
1 2
1 3
2 4
2 5
1 2 2
2 4 3
1 1 1
2 5 3
2 4 5

3
8
10