Alice and Bob are playing a game.

The game is played on a tree with $n$ nodes. Initially, each node has only one number, which is $123456789123456789$.

Sometimes, Alice chooses a path from $s$ to $t$ and adds a number to every node on this path. For a node $r$ on the path, if the distance between $r$ and $s$ is $dis$, then the number Alice adds to node $r$ is $a \cdot dis + b$.

Sometimes, Bob chooses a path from $s$ to $t$. He needs to first select a node on this path, and then select a number from that node.

Bob wants to choose the smallest possible number, but the large amount of numbers makes him dizzy. Bob needs your help to find the minimum number he can choose.

Input

The first line contains two integers $n$ and $m$, representing the number of nodes in the tree and the number of operations.

The next $n-1$ lines each contain three integers $u, v, w$, representing an edge between $u$ and $v$ with length $w$.

The next $m$ lines each start with an integer $1$ or $2$.

If the first number is $1$, it means Alice performs an operation, followed by four integers $s, t, a, b$.

If the first number is $2$, it means Bob performs an operation, followed by two integers $s, t$.

Output

For each operation performed by Bob, output one integer per line, representing the minimum number he can choose.

Examples

Input 1

3 5
1 2 10
2 3 20
2 1 3
1 2 3 5 6
2 2 3
1 2 3 -5 -6
2 2 3

Output 1

123456789123456789
6
-106

Data Scale and Conventions

For all data, $|b| \le 10^9$ and $1 \le w \le 10^9$.