KOI 村由 $N$ 个房屋以及连接房屋的 $N-1$ 条双向道路组成，任意两个不同的房屋之间都可以通过道路相互到达。也就是说，KOI 村的道路网构成了一棵树。

KOI 村的房屋编号为 $0$ 到 $N-1$，道路编号为 $0$ 到 $N-2$。对于所有 $0 \le i \le N-2$，编号为 $i$ 的道路连接房屋 $A[i]$ 和房屋 $B[i]$，长度为 $D[i]$ 米。

最近，KOI 村频繁发生盗窃事件，居民们深受困扰。因此，KOI 村决定在某个房屋安排警察驻守，以应对小偷出现的情况。KOI 村的居民们想知道，在发生盗窃时，警察能以多快的速度抓住小偷。

给定 $Q$ 个场景。场景编号为 $0$ 到 $Q-1$。每个场景包含以下信息：

• 在第 $j$ 个场景中，警察从房屋 $P[j]$ 出发，每秒最多可以移动 $V1[j]$ 米。
• 在第 $j$ 个场景中，小偷从房屋 $T[j]$ 出发，每秒最多可以移动 $V2[j]$ 米。
• 警察出发的房屋与小偷出发的房屋不同，即 $P[j] \neq T[j]$。
• 房屋的大小足够小，因此视为点。道路的宽度足够窄，因此视为线段。道路之间不会交叉。
• 警察和小偷都可以在各自的最大速度内自由地在 KOI 村内移动。也可以选择不移动。
• 如果警察和小偷处于同一位置，警察就能抓住小偷。此时，不仅可以在房屋处，也可以在道路的中间抓住小偷。
• 在场景中，警察和小偷都知道自己和对方的速度，并且在任何时刻都能知道对方的位置。
• 警察和小偷都采取最优策略。即警察采取最快抓住小偷的策略，小偷采取尽可能长时间逃跑的策略。可以证明，当警察和小偷都采取最优策略时，小偷一定会在有限时间内被抓住。

你需要计算每个场景中小偷被抓住所需的时间。

实现细节

你需要实现以下函数：

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$：大小为 $N-1$ 的整数数组。对于所有 $0 \le i \le N-2$，编号为 $i$ 的道路连接房屋 $A[i]$ 和房屋 $B[i]$，长度为 $D[i]$ 米。
• $P, V1, T, V2$：大小为 $Q$ 的整数数组。对于所有 $0 \le j \le Q-1$，在第 $j$ 个场景中，警察从房屋 $P[j]$ 出发，每秒最多移动 $V1[j]$ 米；小偷从房屋 $T[j]$ 出发，每秒最多移动 $V2[j]$ 米。
• 该函数应返回一个大小为 $Q$ 的数组 $C$，其中每个元素都是一个大小为 $2$ 的数组。对于所有 $0 \le j \le Q-1$，第 $j$ 个场景中小偷被抓住的时间（以秒为单位）应表示为分数 $C[j][0]/C[j][1]$。
• $C[j][0]/C[j][1]$ 不一定需要是最简分数。但 $C[j][0]$ 和 $C[j][1]$ 必须是 $1$ 以上且 $10^{18}$ 以下的整数。可以证明，对于满足约束条件的所有输入，答案总是可以用这种形式的分数表示。

提交的源代码中不得执行任何输入输出函数。

数据范围

• $2 \le N \le 100\,000$
• $1 \le Q \le 100\,000$
• 对于所有 $0 \le i \le N-2$，$0 \le A[i], B[i] \le N-1, A[i] \neq B[i]$
• 对于所有 $0 \le i \le N-2$，$1 \le D[i] \le 1\,000\,000$
• KOI 村构成树结构。
• 对于所有 $0 \le j \le Q-1$，$0 \le P[j], T[j] \le N-1, P[j] \neq T[j]$
• 对于所有 $0 \le j \le Q-1$，$1 \le V1[j], V2[j] \le 1\,000\,000$

子任务

1. (15分) $N \le 5\,000, Q \le 5\,000$
2. (21分) $N \le 50\,000, Q \le 50\,000$
3. (5分) 对于所有 $0 \le i \le N-2$，$A[i] = i, B[i] = i+1$
4. (6分) 对于所有 $0 \le i \le N-2$，$A[i] = 0, B[i] = i+1$
5. (14分) 对于所有 $0 \le j \le Q-1$，$V1[j] \le V2[j]$
6. (9分) 对于所有 $0 \le j \le Q-1$，连接 $P[j]$ 号房屋和 $T[j]$ 号房屋的简单路径上的道路数量不超过 $10$ 条
7. (9分) 对于所有 $0 \le j \le Q-1$，$P[j] = 0$
8. (10分) 对于所有 $0 \le j \le Q-1$，$T[j] = 0$
9. (11分) 无额外约束条件。

样例

输入格式 1

4 3
0 1 557912
0 2 517656
0 3 275807
3 265381 0 1000000
0 190435 2 12345
0 195025 3 67890

输出格式 1

833719 265381
517656 190435
275807 195025

输入格式 2

6 4
0 1 2
1 2 2
2 3 10
1 4 8
2 5 16
3 4 0 3
3 2 0 1
3 19 0 9
3 20 0 19

输出格式 2

6 1
10 1
1 1
13 10