Problem Description

We have a tree $\langle V,E\rangle$ consists of $n$ vertices with weight $a_i (i \in V)$ on the vertices and weight $b_e (e=\langle u,v\rangle \in E)$ on the bidirectional edges. $a_i$ is a non-negative integer and $b_e$ is an integer.

You can perform no more than $4n$ following operations:

For the shortest path from $x$ to $y$ traveling $k+1$ vertices $(v_0,v_1,v_2,...,v_k)$ where $v_0 = x ,v_k = y$, let $e_i=\langle v_{i},v_{i+1}\rangle (0 \leq i < k)$. In one operation, you can choose $2$ vertices $x,y$ and a non-negative integer $w$, to make:
$$a_x \leftarrow a_x \bigoplus w;\quad a_y \leftarrow a_y \bigoplus w;\quad b_{e_i}\leftarrow b_{e_i} + (-1) ^ i w \, (0 \leq i < k)$$
Where $\bigoplus$ denotes the bitwise XOR operation. We can notice that if $x=y$, nothing will change.

You need to decide whether it is possible to make all $a_i,b_{e}$ equal to $0$. If it is possible, output a solution using no more than $4n$ operations described above.

Input

The first line contains an integer $T(1 \leq T \leq 250)$ - the number of test cases. Then $T$ test cases follow.

The first line of each test case contains a single integer $n(1 \leq n \leq 10^4)$ - the number of vertices.

The following line contains $n$ non-negative integers $a_i(0 \leq a_i < 2^{30})$ - the weight on each vertex.

Then $n-1$ lines follow, each line contains three integers $x_j,y_j,w_j(1 \leq x_j,y_j \leq n,-10^9 \leq w_j \leq 10^9)$, representing an edge between vertices $x_j,y_j$ with weight $w_j$. It is guaranteed that the given edges form a tree.

It is guaranteed that $\sum n \leq 10^5$.

Output

For each test case, output "YES'' in the first line if you can make all $a_i,b_{e}$ equal to $0$ with no more than $4n$ operations. Output "NO'' otherwise.

If you can make all weights equal to $0$, output your solution in the following $k+1 (0 \leq k \leq 4n)$ lines as follows.

The first line contains one integer $k$ - the number of operations you make.

Then $k$ lines follow, each line contains $3$ integers $X_j,Y_j,W_j(1 \leq X_j, Y_j \leq n,0 \leq W_j \leq 10^{14})$, representing one operation.

If there are multiple possible solutions, output any.

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

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