Alice and Bob's Tree Game

Alice and Bob are playing a game on a tree with \(n\) nodes. Initially, each node \(i\) contains the number \(123456789123456789\). There are two types of operations:

• Alice's operation (Update): Given two nodes \(s\) and \(t\), consider the simple path from \(s\) to \(t\). For each node \(r\) on the path, if its distance from \(s\) (in number of edges along the path) is \(dis\), then add the value \(a \times dis + b\) to node \(r\). (Both \(a\) and \(b\) are given integers.)
• Bob's operation (Query): Given two nodes \(s\) and \(t\), Bob chooses the simple path between \(s\) and \(t\) and then selects the smallest number among all nodes on that path.

You are to process \(q\) operations. Each operation is in one of the following formats:

• For an update operation: 1 s t a b
• For a query operation: 2 s t

Note:

• The tree is undirected, and it is guaranteed that there exists a unique simple path between any two nodes.
• All nodes are numbered from \(1\) to \(n\).

inputFormat

The first line contains two integers \(n\) and \(q\) \((2 \le n, q \le 1000)\), representing the number of nodes and the number of operations.

Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) \((1 \le u,v \le n)\) representing an edge connecting nodes \(u\) and \(v\).

Each of the next \(q\) lines represents an operation in one of the following formats:

• 1 s t a b — an update operation. \(a\) and \(b\) are integers.
• 2 s t — a query operation.

outputFormat

For each query operation, output a single line containing the smallest number on the nodes along the specified path.

sample

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

123456789123456789
123456789123456789