+ محدودیت زمان: ۲ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
امیرحسین و محمدسام درختی پیدا کردهاند و به دلیل اعصاب خرابشان دقیقاً نمیدانند که چه کاری میخواهند با این درخت انجام دهند. ابتدا امیرحسین به رأس $u$ یک مقدار $a_u$ نسبت میدهد. میدانیم امتیاز $path(u, v)$ برابر است با:
\[
\frac{\sum_{w \in \operatorname{path}(u,v)} a_w}{\operatorname{len}(u,v)}
\]
که در آن $path(u, v)$ کوتاهترین مسیر از رأس $u$ به رأس $v$ است و $len(u, v)$ تعداد رأسهای موجود در $path(u, v)$ را نشان میدهد.
در ادامه محمدسام یک عدد $k$ انتخاب میکند و سپس در $q$ مرحله مقدار بعضی از رأسها را افزایش میدهد. شما باید پس از هر درخواست، در میان تمامی مسیرهایی که حداقل $k$ رأس دارند، بیشترین امتیاز ممکن را پیدا کنید.
توجه کنید که هر عملیات روی درختی انجام میشود که تمام تغییرات مراحل قبل روی آن اعمال شده است.
# ورودی
شما باید مسئله را برای $T$ تستکیس مستقل حل کنید.
در خط اول، عدد $T$ داده میشود.
برای هر تستکیس:
- در خط اول دو عدد $n$ و $k$، بهترتیب تعداد رأسهای درخت و عدد انتخابی محمدسام، داده میشود.
- در خط دوم، $n$ عدد داده میشود که مقدار $a_i$ را برای هر رأس مشخص میکنند.
- در $n-1$ خط بعد، هر خط شامل دو عدد $v_i$ و $u_i$ است که دو سر یالهای درخت را مشخص میکنند.
- در خط بعد، عدد $q$ داده میشود که تعداد تغییرات را نشان میدهد.
- در $q$ خط بعد، هر خط شامل دو عدد $v_i$ و $x_i$ است؛ یعنی در این مرحله مقدار رأس $v_i$ به اندازه $x_i$ افزایش مییابد.
$$1 \leq T \leq 10^5$$
$$1 \leq n \leq 10^5$$
$$1 \leq k \leq 10$$
$$1 \leq q \leq 10^4$$
$$1 \leq a_i, x_i \leq 10^9$$
تضمین میشود که مجموع مقادیر $n$ در تمامی تستکیسها از $3 \times 10^5$ و مجموع مقادیر $q$ از $3 \times 10^4$ بیشتر نخواهد شد.
# خروجی
برای هر پرسش، پاسخ را به صورت $A/B$ چاپ کنید، بهطوری که:
$$gcd(A,B)=1$$
# مثال
## ورودی نمونه ۱
```text
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
```
## خروجی نمونه ۱
```text
31/2
31/2
22/1
27/1
27/1
27/1
1000000027/1
```