Police and Thief

KOI Village has $N$ houses and $N - 1$ two-way roads connecting them. Any two different houses can reach each other using only roads. In other words, the road network of KOI Village forms a tree.

The houses are numbered differently from $0$ to $N - 1$, and the roads are numbered differently from $0$ to $N - 2$. For every $0 \le i \le N - 2$, road $i$ connects house $A[i]$ and house $B[i]$, and its length is $D[i]$ meters.

Recently, thieves have often broken into KOI Village, and residents are having a hard time. To prepare for this, a police officer is posted at one house in KOI Village so they can respond when a thief appears. The residents want to know how quickly the police can catch a thief during a break-in.

You are given $Q$ scenarios. The scenarios are numbered differently from $0$ to $Q - 1$. Each scenario works as follows.

• In scenario $j$, the police start at house $P[j]$ and can move at most $V1[j]$ meters per second.
• In scenario $j$, the thief starts at house $T[j]$ and can move at most $V2[j]$ meters per second.
• The house where the police start and the house where the thief starts are different. That is, $P[j] \ne T[j]$.
• Houses are treated as points because they are small enough. Roads are treated as line segments because they are narrow enough. Roads do not cross each other.
• The police and the thief can each move freely within KOI Village, up to their maximum speeds. Staying still is also allowed.
• If the police are at the same position as the thief, the police can catch the thief. The police can catch the thief not only at a house but also in the middle of a road.
• In a scenario, the police and the thief know their own speed and the other's speed, and at any moment they can know the other's position.
• The police and the thief use their best strategies. The police use the strategy that catches the thief fastest, and the thief uses the strategy that keeps running for the longest time. When both use their best strategies, it can be proven that the thief is caught in finite time.

For each scenario, find the time it takes for the police to catch the thief.

• $2 \le N \le 100\,000$
• $1 \le Q \le 100\,000$
• For all $0 \le i \le N - 2$, $0 \le A[i], B[i] \le N - 1$ and $A[i] \ne B[i]$
• For all $0 \le i \le N - 2$, $1 \le D[i] \le 1\,000\,000$
• The road network of KOI Village forms a tree.
• For all $0 \le j \le Q - 1$, $0 \le P[j], T[j] \le N - 1$ and $P[j] \ne T[j]$
• For all $0 \le j \le Q - 1$, $1 \le V1[j], V2[j] \le 1\,000\,000$