The KOI village consists of $N$ houses and $N-1$ bidirectional roads connecting them, such that any two distinct houses can be reached from each other using only the roads. In other words, the road network of the KOI village forms a tree structure.

The houses in the KOI village are numbered from $0$ to $N-1$, and the roads are numbered from $0$ to $N-2$. For every $0 \le i \le N-2$, the $i$-th road connects house $A[i]$ and house $B[i]$ with a length of $D[i]$ meters.

Recently, thieves have frequently entered the KOI village, causing difficulties for the residents. To prepare for when a thief appears, the residents plan to have a police officer stationed at one of the houses. The people of the KOI village are curious about how quickly the police officer can catch a thief when one appears.

You are given $Q$ scenarios. The scenarios are numbered from $0$ to $Q-1$. Each scenario consists of the following:

• In the $j$-th scenario, the police officer starts at house $P[j]$ and can move at a maximum speed of $V1[j]$ meters per second.
• In the $j$-th scenario, the thief starts at house $T[j]$ and can move at a maximum speed of $V2[j]$ meters per second.
• The house where the police officer starts and the house where the thief starts are different. That is, $P[j] \neq T[j]$.
• Since the size of a house is sufficiently small, houses are treated as points. Since the width of a road is sufficiently narrow, roads are treated as line segments. Roads do not intersect.
• The police officer and the thief can each move freely within the KOI village within their respective maximum speeds. It is also possible for them not to move.
• If the police officer is at the same location as the thief, the police officer can catch the thief. At this time, it is possible to catch the thief not only at a house but also in the middle of a road.
• Within a scenario, the police officer and the thief know their own speed and the speed of the other, and they know the location of the other at any point in time.
• The police officer and the thief use optimal strategies. That is, the police officer uses a strategy to catch the thief as quickly as possible, and the thief uses a strategy to escape for as long as possible. It can be proven that when the police officer and the thief use their optimal strategies, the thief will always be caught within a finite amount of time.

You must find the time it takes for the thief to be caught for each scenario.

Implementation Details

You must implement the following function:

vector< array<long long, 2> > police_thief(vector<int> A, vector<int> B,
vector<int> D, vector<int> P, vector<int> V1, vector<int> T, vector<int> V2)

• $A, B, D$: Integer arrays of size $N-1$. For every $0 \le i \le N-2$, the $i$-th road connects house $A[i]$ and house $B[i]$ with a length of $D[i]$ meters.
• $P, V1, T, V2$: Integer arrays of size $Q$. For every $0 \le j \le Q-1$, in the $j$-th scenario, the police officer starts at house $P[j]$ and can move at a maximum speed of $V1[j]$ meters per second, and the thief starts at house $T[j]$ and can move at a maximum speed of $V2[j]$ meters per second.
• This function must return an array $C$ of size $Q$, where each element is an array of size $2$. For every $0 \le j \le Q-1$, the time (in seconds) it takes for the thief to be caught in the $j$-th scenario must be represented as the fraction $C[j][0]/C[j][1]$.
• $C[j][0]/C[j][1]$ does not need to be an irreducible fraction. However, $C[j][0]$ and $C[j][1]$ must be integers between $1$ and $10^{18}$ inclusive. It can be proven that for all inputs satisfying the constraints, the answer can always be expressed as a fraction of this form.

Do not execute any input/output functions in any part of the submitted source code.

Constraints

• $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$, $A[i] \neq B[i]$
• For all $0 \le i \le N-2$, $1 \le D[i] \le 1\,000\,000$
• The KOI village forms a tree structure.
• For all $0 \le j \le Q-1$, $0 \le P[j], T[j] \le N-1$, $P[j] \neq T[j]$
• For all $0 \le j \le Q-1$, $1 \le V1[j], V2[j] \le 1\,000\,000$

Subtasks

1. (15 points) $N \le 5\,000$, $Q \le 5\,000$
2. (21 points) $N \le 50\,000$, $Q \le 50\,000$
3. (5 points) For all $0 \le i \le N-2$, $A[i] = i, B[i] = i+1$
4. (6 points) For all $0 \le i \le N-2$, $A[i] = 0, B[i] = i+1$
5. (14 points) For all $0 \le j \le Q-1$, $V1[j] \le V2[j]$
6. (9 points) For all $0 \le j \le Q-1$, the number of roads on the simple path between house $P[j]$ and house $T[j]$ is at most $10$
7. (9 points) For all $0 \le j \le Q-1$, $P[j] = 0$
8. (10 points) For all $0 \le j \le Q-1$, $T[j] = 0$
9. (11 points) No additional constraints.

Examples

Example 1

Input 1

N = 4, Q = 3, A = [0, 0, 0], B = [1, 2, 3], D = [557912, 517656, 275807],
P = [3, 0, 0], V1 = [265381, 190435, 195025], T = [0, 2, 3], V2 = [1000000, 12345, 67890]

Output 1

[[833719, 265381], [517656, 190435], [275807, 195025]]

Example 2

Input 2

N = 6, Q = 4, A = [0, 1, 2, 1, 2], B = [1, 2, 3, 4, 5], D = [2, 2, 10, 8, 16],
P = [3, 3, 3, 3], V1 = [4, 2, 19, 20], T = [0, 0, 0, 0], V2 = [3, 1, 9, 19]

Output 2

[[6, 1], [10, 1], [1, 1], [13, 10]]

Example 3

Input 3

N = 10, Q = 10, A = [4, 2, 9, 9, 3, 7, 1, 6, 5], B = [9, 8, 0, 1, 1, 6, 2, 2, 9], D = [7, 8, 4, 5, 1, 2, 5, 10, 2],
P = [3, 0, 5, 2, 0, 5, 5, 7, 9, 8], V1 = [1, 6, 6, 5, 2, 6, 5, 4, 1, 5],
T = [5, 5, 9, 1, 6, 2, 0, 1, 8, 4], V2 = [9, 7, 6, 7, 4, 10, 10, 8, 7, 5]

Output 3

[[18, 1], [13, 3], [4, 1], [17, 5], [13, 1], [4, 1], [6, 5], [29, 4], [22, 1], [5, 1]]

Example 4

Input 4

N = 10, Q = 10, A = [6, 8, 8, 3, 4, 9, 0, 1, 8], B = [7, 5, 2, 9, 1, 7, 4, 3, 4], D = [1, 1, 4, 4, 4, 7, 3, 4, 7],
P = [3, 1, 6, 2, 3, 3, 2, 6, 1, 2], V1 = [5, 7, 9, 7, 5, 10, 8, 8, 4, 8],
T = [0, 7, 8, 0, 2, 0, 0, 7, 8, 5], V2 = [2, 2, 5, 5, 4, 5, 7, 2, 2, 7]

Output 4

[[11, 5], [16, 7], [31, 9], [4, 1], [19, 5], [11, 10], [31, 8], [1, 6], [15, 4], [3, 1]]

Sample grader

The sample grader receives input in the following format:

• Line 1: $N$ $Q$
• Line $2 + i$ ($0 \le i \le N-2$): $A[i]$ $B[i]$ $D[i]$
• Line $1 + N + j$ ($0 \le j \le Q-1$): $P[j]$ $V1[j]$ $T[j]$ $V2[j]$

Let $C$ be the array returned by police_thief. The sample grader outputs the following:

• Line $1 + j$ ($0 \le j \le Q-1$): $C[j][0]$ $C[j][1]$

Note that the sample grader may differ from the grader used in actual grading.