给定一棵包含 $n$ 个顶点的树 $V, E$，顶点编号为 $1$ 到 $n$。每个顶点 $i \in V$ 都有一个权值 $a_i$。每条双向边 $e = (u, v) \in E$ 都有一个权值 $b_e$。其中，$a_i$ 为非负整数，$b_e$ 为整数。

你可以执行最多 $4n$ 次操作。每次操作选择两个顶点 $X$ 和 $Y$，以及一个非负整数 $W$。考虑从 $X$ 到 $Y$ 的最短路径（若路径包含的边数 $k$ 最少，则称其为最短路径）。设该路径包含 $k+1$ 个顶点 $(v_0, v_1, v_2, \dots, v_k)$，其中 $v_0 = X$，$v_k = Y$，且对于 $0 \le i < k$，边 $e_i = (v_i, v_{i+1}) \in E$。该操作按如下方式改变权值：

$a_X \leftarrow a_X \oplus W; \quad a_Y \leftarrow a_Y \oplus W; \quad b_{e_i} \leftarrow b_{e_i} + (-1)^i \cdot W \quad \text{对于 } 0 \le i < k$

其中，$\oplus$ 表示按位异或运算。注意，若 $X = Y$，则权值不会发生任何变化。

你需要判断是否可以将所有的 $a_i$ 和所有的 $b_e$ 都变为 $0$。如果可以，请给出一种方案。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 250$)，表示测试用例的数量。接下来是 $T$ 个测试用例。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 10^4$)，表示顶点数。

第二行包含 $n$ 个非负整数 $a_i$ ($0 \le a_i < 2^{30}$)，表示每个顶点的权值。

接下来 $n-1$ 行，每行包含三个整数 $u_j, v_j, w_j$ ($1 \le u_j, v_j \le n, -10^9 \le w_j \le 10^9$)，表示连接顶点 $u_j$ 和 $v_j$ 的权值为 $w_j$ 的边。保证给定的边构成一棵树。

保证 $\sum n \le 10^5$。

输出格式

对于每个测试用例，如果能在不超过 $4n$ 次操作内将所有 $a_i$ 和 $b_e$ 变为 $0$，则第一行输出 “YES”，否则输出 “NO”。

如果可以将所有权值变为 $0$，请按以下格式输出你的方案，共 $k+1$ 行 ($0 \le k \le 4n$)：

下一行输出一个整数 $k$，表示你执行的操作次数。

接下来 $k$ 行，每行包含三个整数 $X, Y, W$ ($1 \le X, Y \le n, 0 \le W \le 10^{14}$)，表示一次操作。

如果存在多种方案，输出任意一种即可。

样例

样例输入 1

3
1
0
2
2 3
1 2 -2
3
5 4 1
1 2 -5
2 3 -5

样例输出 1

YES
0
NO
YES
3
1 3 5
2 3 7
2 3 3