White Falcon has a tree with nodes. Each node contains a linear function. Let's denote by the linear function contained in the node .

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

White Falcon also has queries. They are in the following format:

. Assign as the function of all the nodes on the path from to , i.e., is changed to where is the path from to .

. Calculate modulo

**Input Format**

The first line contains , the number of nodes. The following lines each contain two integers and that describe the function .

Following lines contain edges of the tree.

The next line contains , the number of queries. Each subsequent line contains one of the queries described above.

**Output Format**

For every query of the second kind, print one line containing an integer, the answer for that query.

**Constraints**

(Number of nodes)

(Number of queries)

**Sample Input**

```
2
1 1
1 2
1 2
2
1 2 2 1 1
2 1 2 1
```

**Sample Output**

```
3
```

**Explanation**