Average

Problem Description

You are given a tree with $n$ nodes. Every node has its value $a_u$. The value of a $path(u,v)$ on the tree is equal to $$\frac{\sum_{w \in path(u,v)} a_w}{len(u,v)}$$ where $path(u,v)$ is the shortest path from $u$ to $v$, $len(u,v)$ means the number of nodes in $path(u,v)$. You have to answer questions like what is the maximum possible value of a path with length greater than or equal to $k$. Unfortunately, the value of nodes will increase. So you need to answer the question after each change.

Input

Each test contains multiple test cases. The first line contains an integer $T(1 \leq T \leq 10^5)$, indicating the number of test cases. The description of test cases follows. The first line contains two integers $n$,$k$ $(1 \leq n \leq 10^5,1 \leq k \leq 30)$. The second line contains $n$ integers $a_i(1 \leq a_i \leq 10^9)$. The following $n-1$ lines contains $2$ integers $u_i$ and $v_i$ $(1 \leq u_i,v_i \leq n,u_i \neq v_i)$, indicating an edge between vertices $u_i$ and $v_i$. It is guaranteed that the given edges form a tree. The next line contains a integer $q$ $(1 \leq q \leq 10^4)$. The following $q$ lines contains $2$ integers $u_i, x$ $(1 \leq u_i \leq n, 1 \leq x \leq 10^9)$, indicating that the value of node $u_i$ will increase $x$. It is guaranteed that the sum of $n$ over all test cases does not exceed $3.5\times 10^5$, and the sum of $q$ over all test cases does not exceed $4\times 10^4$.

Output

Output the answer $A/B$, indicating the value is $\frac{A}{B}$ and $\gcd(A,B)=1$. If no such path, output "$0/1$".

Sample Input

2
6 2
6 16 6 15 5 4
1 2
2 3
2 4
2 5
4 6
2
1 4
3 5
14 1
12 19 9 17 9 10 11 18 9 19 10 14 18 8
1 2
2 3
1 4
1 5
4 6
2 7
7 8
8 9
6 10
6 11
1 12
11 13
3 14
5
10 3
2 8
7 9
5 6
2 1000000000

Sample Output

31/2
31/2
22/1
27/1
27/1
27/1
1000000027/1

Source

2023“钉耙编程”中国大学生算法设计超级联赛（9）