Heavy Light 2 White Falcon

White Falcon was amazed by what she can do with heavy-light decomposition on trees. As a resut, she wants to improve her expertise on heavy-light decomposition. Her teacher gave her an another assignment which requires path updates. As always, White Falcon needs your help with the assignment.

You are given a tree with nodes and each node's value is initially .

Let's denote the path from node to node like this: , where and , and and are connected.

The problem asks you to operate the following two types of queries on the tree:

"1 u v x" Add to , to , to , ..., to .
"2 u v" print the sum of the nodes' values on the path between and at modulo .

Input Format

First line cosists of two integers and seperated by a space.
Following lines contains two integers which denote the undirectional edges of the tree.
Following lines contains one of the query types described above.

Note: Nodes are numbered by using 0-based indexing.

Constraints

Output Format

For every query of second type print a single integer.

Sample Input

Sample Output

Explanation

After the first type of query, . Hence the answer of the second query is .