给定一棵包含 $n$ 个顶点和 $n-1$ 条边的无向树。 第 $i$ 个顶点有一个正整数权值 $a_i (i = 1, 2, \dots, n)$。 第 $i$ 条边有一个正整数权值 $k_i (i = 1, 2, \dots, n-1)$。

我们定义 $f(x, T)$ 为树 $T$ 中权值等于 $x$ 的顶点总数。 我们定义 $g(y, T)$ 为满足 $f(x, T) \ge y$ 的最大 $x$ 值；若不存在满足条件的 $x$，则 $g(y, T) = 0$。

对于第 $i$ 条边，如果我们将其删除，原树将被分成两棵新树，分别记为 $T_{i1}$ 和 $T_{i2}$。 对于第 $i$ 条边，你需要计算 $\max(g(k_i, T_{i1}), g(k_i, T_{i2})) (i = 1, 2, \dots, n-1)$。 请注意，对于每一条边，我们并不会真正将其删除。 请注意程序的运行时间复杂度。

输入格式

每个测试包含多个测试用例。输入的第一行包含一个整数 $t (1 \le t \le 10^6)$，表示测试用例的数量。接下来是各测试用例的描述。 每个测试用例的第一行包含一个整数 $n (1 \le n \le 10^6)$，表示顶点数量。 每个测试用例的第二行包含 $n$ 个整数 $a_i (1 \le a_i \le 10^9)$，表示每个顶点的权值。 接下来的 $n-1$ 行，每行包含三个整数 $u_i, v_i$ 和 $k_i (1 \le u_i, v_i, k_i \le n, u_i \neq v_i)$，表示连接顶点 $u_i$ 和 $v_i$ 且权值为 $k_i$ 的边。保证给定的边构成一棵树。 保证所有测试用例的 $n$ 之和不超过 $3 \times 10^6$。

输出格式

对于每个测试用例，输出 $n-1$ 行，其中第 $i$ 行包含一个整数，表示第 $i$ 条边的答案。

说明

在本题中，你可能需要更多的栈空间来通过测试。如果你使用 C++，建议在 main 函数中加入以下代码：

int main() {
int size(512<<20); // 512M
__asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size));
// YOUR CODE
...
exit(0);
}

如果你使用了上述代码，请务必在 main 函数末尾添加 exit(0);，否则你的代码可能会出现 RE（运行时错误）。

样例

样例输入 1

3
5
5 2 1 2 2
3 4 2
3 2 1
2 1 1
2 5 1
5
2 1 3 1 5
2 4 1
2 1 2
1 3 2
1 5 3
1
3

样例输出 1

2
5
5
5
5
1
1
0