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**

```
3 2
0 1
1 2
1 0 2 1
2 1 2
```

**Sample Output**

```
5
```

**Explanation**

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