Cho cây ~n~ đỉnh, mỗi đỉnh được tô một trong ~2~ màu trắng hoặc đen. Một cặp đỉnh ~(u, v)~ có thể ghép đôi với nhau khi và chỉ khi thỏa mãn đồng thời:

• ~u~ và ~v~ được tô màu trắng

• Các đỉnh trên đường đi đơn của từ ~u \rightarrow v~ được tô toàn màu đen (trừ ~u~ và ~v~)

Yêu cầu tô màu đỉnh của cây sao cho tạo được nhiều cặp ~(u, v)~ có thể ghép đôi với nhau nhất.

Input

Dòng đầu tiên chứa một số nguyên dương (~T \leq 10~) là số lượng test.

Ở mỗi test:

• Dòng đầu tiên của test chứa số nguyên dương ~N~ (~N \leq 5000~) là số lượng nút của cây.

• ~N - 1~ dòng tiếp theo chứa hai số nguyên ~u, v~ (~1 \leq u, v \leq n~) là cạnh của cây. Dữ liệu đảm bảo đồ thị sẽ là cây

Output

Ghi ra ~T~ dòng, mỗi dòng chứa một số nguyên là kết quả tương ứng với bộ test.

Sample Input 1

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

Sample Output 1

5
2

Sample Input 2

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

Sample Output 2

2
6

Notes

Ở ví dụ 1, test đầu tiên, ta tô màu đỉnh ~2~ để có được ~5~ cặp ~(1, 4)~, ~(1, 3)~, ~(3, 4)~, ~(3, 6)~, ~(5, 6)~.

Ở ví dụ 2, test thứ hai, ta cũng tô màu đỉnh ~2~ để có được ~6~ cặp ~(1, 3)~, ~(1, 4)~, ~(1, 5)~, ~(3, 4)~, ~(3, 5)~, ~(4, 5)~.

Có ~N~ giám khảo và ~M~ thí sinh. Giám khảo thứ ~i~ sẽ bầu chọn cho thí sinh thứ ~j~ nếu ~A_{i,j} = 1~, và không bầu chọn nếu ~A_{i,j} = 0~. Một thí sinh sẽ được chọn nếu họ được ~\geq \lfloor \frac{N}{2} \rfloor~ giám khảo bầu chọn cho mình.

Tuy nhiên sẽ có 2 ông giám khảo ~i~ và ~j~ bất kì (~i \neq j~) bị loại ra để kiểm phiếu. Với mỗi giám khảo ~i~, bạn cần tính xem: nếu như bạn phải loại giám khảo ~i~, và một giám khảo ~j~ bất kì khác (~j \neq i~), thì số người được chọn lớn nhất là bao nhiêu?

Input

• Dòng đầu tiên chứa hai số ~N~ và ~M~. (~3 \leq N \leq 3 \times 10^5~, ~1 \leq M \leq 20~)

• Dòng thứ ~i~ trong số ~N~ dòng tiếp theo chứa ~M~ số nguyên không âm, với số thứ ~j~ là ~A_{i, j}~. (~A_{i, j} \in \{0, 1\}~)

Output

• Gồm ~N~ dòng, dòng thứ ~i~ chứa một số nguyên duy nhất là kết quả khi bắt buộc phải chọn giám khảo ~i~ đi kiểm phiếu.

Sample Input 1

3 3
1 0 1
1 1 1
0 1 0

Sample Output 1

3
2
3

Sample Input 2

4 10
1 1 0 1 0 0 0 1 1 0
1 1 1 0 0 1 1 1 0 0
0 0 0 1 0 0 0 1 1 1
0 1 1 1 0 0 0 0 1 0

Sample Output 2

2
3
3
3

Bạn đang mắc kẹt trong một mê cung gồm ~n~ căn phòng, được đánh số từ ~1~ đến ~n~. Mê cung này có cấu trúc dạng cây, với phòng số ~1~ là gốc.

Phòng thứ ~i~ có hai giá trị đặc biệt: ~a_i~ và ~b_i~. Từ phòng ~u~, bạn có thể nhảy đến bất kì phòng nào nằm trong cây con gốc ~u~, trừ chính đỉnh ~u~. Chi phí để nhảy từ phòng ~x~ đến ~y~ là ~a_x \cdot b_y~.

Nhiệm vụ của bạn là với mọi phòng ~u~, tính chi phí nhỏ nhất để thoát khỏi mê cung nếu xuất phát từ đỉnh ~u~ và kết thúc tại một nút lá (là một nút có bậc bằng ~1~, trừ nút gốc) bất kì.

Input

• Dòng đầu tiên chứa một số nguyên dương ~n~ (~2 \leq n \leq 10^5~) – số lượng đỉnh trong cây.

• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~-10^5 \leq a_i \leq 10^5~).

• Dòng thứ ba chứa ~n~ số nguyên ~b_1, b_2, \ldots, b_n~ (~-10^5 \leq b_i \leq 10^5~).

• ~n-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u_i~ và ~v_i~ (~1 \leq u_i, v_i \leq n~) mô tả cạnh giữa đỉnh ~u_i~ và ~v_i~ trong cây.

Output

In ra ~n~ số nguyên cách nhau bởi dấu cách, trong đó số thứ ~i~ là chi phí nhỏ nhất để đi từ nút ~i~ đến bất kỳ nút lá nào trong cây con gốc ~i~.

Scoring

Sample Input 1

3
2 10 -1
7 -7 5
2 3
2 1

Sample Output 1

10 50 0

Sample Input 2

4
5 -10 5 7
-8 -80 -3 -10
2 1
2 4
1 3

Sample Output 2

-300 100 0 0

Notes

• Ở test ví dụ đầu tiên, nút ~3~ đã là lá nên chi phí của nó bằng ~0~. Với nút ~2~, ta nhảy thẳng đến nút ~3~ với chi phí ~a_2 \cdot b_3 = 50~. Với nút ~1~, ta nhảy thẳng đến nút ~3~ với chi phí ~a_1 \cdot b_3 = 10~.

• Ở test ví dụ thứ hai, nút ~3~ và ~4~ là lá, nên chi phí bằng ~0~. Với nút ~2~, ta nhảy đến nút ~4~ với chi phí ~a_2 \cdot b_4 = 100~. Với nút ~1~, ta nhảy từ ~1 \rightarrow 2 \rightarrow 4~ với chi phí ~a_1 \cdot b_2 + a_2 \cdot b_4 = -400+100=-300~.

Bạn hiện tại đang có số tiền khởi đầu là ~C~ và đang muốn sử dụng máy in tiền để làm giàu như một vì tinh tú nào đó.

Mỗi ngày được chia ra làm ba buổi với ba công việc khác nhau:

• Buổi sáng: Bán máy in tiền mà bạn đã mua trước đó.

• Buổi chiều: Sử dụng máy in tiền để làm giàu.

• Buổi tối: Mua một máy in tiền khác.

Bạn chỉ được phép có duy nhất một máy in tiền; bạn phải bán máy in tiền cũ trước khi được phép mua cái mới.

Bạn đã có thông tin về ~N~ cái máy in tiền. Máy thứ ~i~ chỉ được bán vào ngày thứ ~D_i~ với giá tiền ~P_i~ và sẽ nhận được giá tiền ~R_i~ sau khi bán máy. Máy này có thể in được ~G_i~ giá trị tiền mỗi ngày.

Hãy tính số tiền nhiều nhất bạn có thể có được khi thực hiện sau ~D~ ngày.

Input

Dòng đầu tiên gồm ba số nguyên dương ~N~, ~C~ và ~D~ (~N \leq 10^5~; ~C, D \leq 10^9~) — lần lượt là số thông tin về máy in tiền, giá tiền khởi điểm và số ngày thực hiện.

Trong ~N~ dòng tiếp theo, dòng thứ ~i~ mô tả thông tin về máy in tiền thứ ~i~. Mỗi dòng gồm bốn số nguyên dương ~D_i~, ~P_i~, ~R_i~ và ~G_i~ (~D_i < D~; ~R_i < P_i \leq 10^9~; ~G_i \leq 10^9~) — lần lượt là ngày máy được bán, giá tiền cần có để mua được máy, giá tiền nhận được sau khi bán máy và giá trị tiền mà máy in được mỗi ngày.

Output

Gồm một dòng duy nhất, là số tiền nhiều nhất có được khi thực hiện sau ~D~ ngày.

Sample Input 1

6 10 20
6 12 1 3
1 9 1 2
3 2 1 2
8 20 5 4
4 11 7 4
2 10 9 1

Sample Output 1

44

Cho một cây có trọng số gồm ~N~ đỉnh và ~N-1~ cạnh. Cạnh thứ ~i~ nối hai đỉnh ~U_i~ và ~V_i~ và có độ dài là ~W_i~.

Cho ~Q~ truy vấn, truy vấn thứ ~i~ có dạng như sau:

• ~X_i~ ~K_i~: Nếu trọng số của tất cả các cạnh có chứa đỉnh ~X_i~ được nhân lên ~K_i~ lần thì đường kính của cây có tổng trọng số là bao nhiêu?

Các truy vấn độc lập, tức là việc thay đổi trọng số của một truy vấn sẽ không ảnh hưởng đến các truy vấn tiếp theo.

Định nghĩa đường kính của cây là đường đi có tổng trọng số lớn nhất của cây.

Input

Dòng đầu tiên là số nguyên dương ~N~ (~2 \le N \le 10^5~) – số đỉnh của cây.

Trong số ~N-1~ dòng tiếp theo, dòng thứ ~i~ gồm ~3~ số nguyên dương ~U_i, V_i~ và ~W_i~ (~1 \le U_i, V_i \le N, 1 \le W_i \le 10^9~), lần lượt là ~2~ đỉnh được nối bởi cạnh và trọng số của cạnh.

Dòng thứ ~N+1~ gồm một số nguyên dương ~Q~ (~1 \le Q \le 10^5~), đại diện cho số truy vấn.

Dòng thứ ~j~ trong số ~Q~ dòng tiếp theo gồm ~2~ số nguyên dương ~X_j~ và ~K_j~ (~1 \le X_j \le N, 1 \le K_j \le 10^9~), là các truy vấn được cho theo mô tả ở trên.

Output

Mỗi dòng trong ~Q~ dòng tiếp theo in ra một số là đáp án của mỗi truy vấn theo mô tả ở trên.

Sample Input 1

7
5 1 2
1 4 2
3 4 1
2 5 3
6 1 6
4 7 2
2
4 3
3 2

Sample Output 1

18
11

Sample Input 2

3
1 2 1000000000
2 3 1000000000
1
2 1000000000

Sample Output 2

2000000000000000000

Notes

Trước khi bước vào ngưỡng cửa đại học, hungnt quyết định lên kế hoạch đi du lịch trong đợt nghỉ hè tại quần đảo VNOI. Trong kì nghỉ này, anh ấy sẽ di chuyển từ hòn đảo này sang hòn đảo khác và tham quan các địa điểm du lịch tại mỗi hòn đảo để tích lũy kiến thức.

Ở quần đảo VNOI có ~n~ hòn đảo, các hòn đảo được đánh số từ ~0~ đến ~n - 1~. Có những cây cầu bắc qua các hòn đảo. Đối với hòn đảo ~i~ (~0 \le i \le n - 1~), có duy nhất một cây cầu nối đảo ~i~ với ~i-1~ và một cây cầu nối đảo ~i~ và ~i + 1~. Đảo ~0~ có một cây cầu nối với đảo ~1~, đảo ~n - 1~ có một cây cầu nối với đảo ~n - 2~.

Mỗi hòn đảo có một số địa điểm tham quan nhất định. hungnt dự kiến đi du lịch ~d~ ngày và muốn tham quan được nhiều địa điểm nhất. Anh ấy đã chọn một hòn đảo làm điểm xuất phát:

• Mỗi ngày anh ấy có thể di chuyển đến một hòn đảo liền kề hoặc tham quan tất cả các địa điểm du lịch của hòn đảo mà anh ấy đang ở, nhưng không thể làm cả hai việc trong cùng một ngày.

• hungnt không bao giờ tham quan một hòn đảo hai lần ngay cả khi anh ấy quay lại thành phố đó sau khi đã rời đi.

Bạn hãy giúp hungnt lên kế hoạch cho chuyến đi để tối đa hóa số lượng địa điểm tham quan mà anh ấy có thể ghé thăm trong khoảng thời gian ~d~ ngày.

Input

• Dòng đầu tiên gồm ba số nguyên ~n, st, d~ (~2 \le n \le 100000, 0 \le st \le n-1, 0 \leq d \leq 2n + \left\lfloor \frac{n}{2} \right\rfloor~) — số lượng hòn đảo, hòn đảo mà hungnt chọn làm điểm xuất phát và số ngày hungnt dự kiến đi du lịch.

• Dòng thứ hai gồm ~n~ số nguyên không âm ~a_0, a_1, a_2, \ldots a_{n - 1}~ (~0 \le a_i \le 10^9~) — lần lượt là số lượng địa điểm của các hòn đảo từ ~0~ đến ~n - 1~.

Output

• Một số nguyên duy nhất là số lượng địa điểm nhiều nhất mà hungnt có thể thăm quan trong ~d~ ngày.

Scoring

Sample Input 1

5 2 7
10 2 20 30 1

Sample Output 1

60

Notes

• Ngày 1, hungnt thăm các địa điểm ở đảo ~2~

• Ngày 2, di chuyển từ đảo ~2~ sang đảo ~3~

• Ngày 3, thăm các địa điểm ở đảo ~3~

• Ngày 4, di chuyển từ đảo ~3~ sang đảo ~2~

• Ngày 5, di chuyển từ đảo ~2~ sang đảo ~1~

• Ngày 6, di chuyển từ đảo ~1~ sang đảo ~0~

• Ngày 7, thăm các địa điểm ở đảo ~0~

• Tổng số lượng địa điểm hungnt đã thăm quan là: ~20 + 30 + 10 = 60~.

Công ty của bạn có ~n~ người. Người thứ ~1~ là chủ tịch, ~n - 1~ người còn lại là nhân viên. Nhân viên thứ ~i~ (với mọi ~2 \leq i \leq n~) có đúng một sếp ~p_i~ ~(1 \leq p_i < i)~.

Hôm nay có ~m~ người bất kỳ đến văn phòng làm việc. Mọi người lần lượt đến văn phòng với thứ tự bất kỳ, và không có hai người đến văn phòng tại cùng một thời điểm. Người thứ ~i~ có mức độ căng thẳng ~f_i~, ban đầu bằng ~0~. Với mỗi ~i \geq 2~:

• Nếu nhân viên ~i~ đến muộn hơn sếp ~p_i~ của họ thì mức độ căng thẳng ~f_{p_i}~ của sếp của nhân viên này sẽ tăng lên một lượng ~a_i~;

• Trái lại, nếu nhân viên ~i~ đến sớm hơn sếp ~p_i~ thì mức độ căng thẳng ~f_i~ của nhân viên này sẽ tăng lên một lượng ~b_i~.

Mức độ căng thẳng của công ty là tổng mức độ căng thẳng của tất cả ~m~ người đến văn phòng: ~\sum_{i=1}^{n} f_i~ Với mỗi ~m~ từ ~1~ đến ~n~, hãy tìm mức độ căng thẳng ít nhất có thể của công ty khi có ~m~ người đi làm hôm nay.

Input

Mỗi test gồm nhiều test case. Dòng đầu tiên chứa số lượng test case ~t~ ~(1 \leq t \leq 1000)~. Mô tả của mỗi test case như sau:

• Dòng đầu tiên chứa một số nguyên ~n~ ~(2 \leq n \leq 2000)~ — số người trong công ty.

• Dòng thứ hai chứa ~n - 1~ số nguyên ~p_2, p_3, \dots, p_n~ ~(1 \leq p_i < i)~ — chỉ số sếp của các nhân viên.

• Dòng thứ ba chứa ~n - 1~ số nguyên ~a_2, a_3, \dots, a_n~ ~(0 \leq a_i \leq 10^5)~ — lượng tăng mức độ căng thẳng của sếp của nhân viên ~i~ nếu nhân viên này đến trễ hơn sếp.

• Dòng thứ tư chứa ~n - 1~ số nguyên ~b_2, b_3, \dots, b_n~ ~(0 \leq b_i \leq 10^5)~ — lượng tăng mức độ căng thẳng của nhân viên ~i~ nếu sếp của nhân viên này đến trễ hơn nhân viên.

Đảm bảo rằng tổng của ~n~ qua tất cả các test case không vượt quá ~2000~.

Output

Với mỗi test case, in ra ~n~ số nguyên, với số thứ ~m~ là mức độ căng thẳng ít nhất có thể của công ty khi có ~m~ người đi làm hôm nay.

Scoring

Sample Input 1

2
5
1 2 2 4
5 8 2 6
6 2 8 8
5
1 2 3 4
7 6 4 9
10 5 5 3

Sample Output 1

0 0 0 6 15 
0 0 0 7 19

Notes

• Nếu hôm nay có ~m = 1~ người đến văn phòng, ta có thể chọn nhân viên bất kỳ đến văn phòng, và mức độ căng thẳng của công ty sẽ là ~0~ vì sẽ không có ai đến trễ hơn ai cả.

• Nếu hôm nay có ~m = 2~ người đến văn phòng, người thứ ~5~ có thể đến đầu tiên, sau đó là người thứ ~1~. Mức độ căng thẳng của công ty sẽ là ~0~ vì người thứ ~1~ và ~5~ không có quan hệ trực tiếp với nhau.

• Nếu hôm nay có ~m = 3~ người đến văn phòng. Người thứ ~1~, ~3~ và ~4~ có thể đến văn phòng theo thứ tự ~1 \to 3 \to 4~. Mức độ căng thẳng của công ty vẫn là ~0~ vì không có hai người nào đến công ty có quan hệ trực tiếp với nhau.

• Với ~m = 4~, ta có thể chọn thứ tự ~1 \to 3 \to 4 \to 5~. Do ~4~ là sếp của ~5~ và ~5~ đến muộn hơn ~4~, sự khó chịu của ~4~ là ~f_4 = 6~. Do đó mức độ căng thẳng của công ty là ~6~.

• Với ~m = 5~, ta có thể chọn thứ tự ~1 \to 3 \to 2 \to 4 \to 5~. Trong trường hợp này, ta có: ~f = [5, 2, 2, 6, 0]~.

  Mức độ căng thẳng của công ty sẽ là ~15~.

Cho một dãy số ~a_1, a_2, ..., a_n~. Dựa trên dãy này, chúng ta có dược dãy số ~b_1, b_2,.., b_n~, sao cho ~b_i=2^{a_i}~ với mọi ~i~.

Một cách phân đoạn hợp lệ là một cách chia dãy ~b_1, b_2,..,b_n~ thành các đoạn con liên tiếp sao cho mỗi phần tử trong dãy thuộc duy nhất một đoạn. Một cách phân đoạn dược gọi là hoàn hảo nếu như tổng của mỗi đoạn là một lũy thừa của ~2~ (lũy thừa có số mũ nguyên).

Bài toán được đưa ra là đếm số cách phân đoạn dãy ~b_1, b_2,..,b_n~ hoàn hảo. Bởi vì đáp án cho bài toán này rất lớn nên bạn hãy in phần dư của nó khi modulo cho ~10^9 + 7~.

Input

Dòng đầu tiên gồm một số nguyên dương ~n~ (~1 \leq n \leq 3 \cdot 10^5~), độ dài của dãy số ~a_1, a_2,...,a_n~ (đồng thời cũng là độ dài của dãy số ~b_1, b_2,...,b_n~).

Dòng tiếp theo gồm ~n~ số nguyên không âm ~a_1, a_2,..., a_n~ (~0 \leq a_i \leq 10^6~).

Output

In ra một dòng duy nhất, là số cách phân đoạn hoàn hảo theo modulo ~10^9 + 7~.

Sample Input 1

5
2 0 0 1 1

Sample Output 1

6

Notes

Trong ví dụ trên, dãy số ~b_1, b_2,...,b_n~ là ~4,1,1,2,2~. Một số cách chia hợp lệ là:

• ~[4], [1], [1], [2], [2]~,

• ~[4], [1, 1], [2], [2]~,

• ~[4], [1], [1], [2, 2]~,

• ~[4], [1, 1], [2, 2]~,

• ~[4], [1, 1, 2], [2]~,

• ~[4, 1, 1, 2], [2]~.

Cho một cây gồm ~n~ đỉnh, mỗi đỉnh ~i~ ứng với một dãy ~m~ bit, bit thứ ~j~ nếu như có món quà loại ~j~ xuất hiện tại đỉnh ~i~ và ngược lại nếu bit thứ ~j = 0~. Loại quà thứ ~j~ được gọi là "trọn vẹn" nếu như bit thứ ~j~ của mọi đỉnh trong tập đỉnh của đồ thị con được bật. Do đó, với mọi đồ thị con của đồ thị ban đầu đều ứng với một số nguyên ~k~ là số món quà được "trọn vẹn". Nhiệm vụ của bạn là đếm xem có bao nhiêu đồ thị con của đồ thị ban đầu cho ra ~k~ món quà "trọn vẹn", với ~k~ từ ~0~ đến ~m~.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ (~1 \leq n \leq 5000, 1 \leq m \leq 10~).

~n - 1~ dòng tiếp theo, mỗi dòng chứa 2 số nguyên ~u, v~ biểu thị một cạnh của đồ thị.

Tiếp theo là ~n~ dòng, dòng thứ ~i~ gồm ~m~ số nguyên tương ứng với dãy bit của các quà tại đỉnh ~i~.

Output

In ra ~m + 1~ số nguyên trên một dòng, số thứ ~k~ là số lượng đồ thị con liên thông sao cho tồn tại đúng ~k~ món quà trọn vẹn. Kết quả chia lấy dư cho ~10^9 + 7~.

Scoring

Sample Input 1

3 2
1 2
1 3
1 0
1 1
0 1

Sample Output 1

2 3 1

Notes

Các đồ thị con liên thông là:

1. ~\{1\}~, loại quà: 1.

2. ~\{2\}~, loại quà: ~\{1, 2\}~.

3. ~\{3\}~, loại quà: 2.

4. ~\{1, 2\}~, loại quà: 1.

5. ~\{1, 3\}~, loại quà: ~\varnothing~.

6. ~\{1, 2, 3\}~, loại quà: ~\varnothing~.

Vì vậy, đáp án là ~[2, 3, 1]~.

Có ~n~ người dân ở trong một thành phố được biểu diễn dưới dạng cây gồm ~n~ đỉnh thể hiện nhà của mỗi người dân cùng ~n-1~ cạnh có trọng số. Khi thảm hoạ xảy ra, ~n~ người dân này cần sơ tán về ~k~ điểm sơ tán theo đường đi ngắn nhất. Do các con đường có sức chứa vô hạn, nên thời gian cho việc sơ tán là thời gian dài nhất mà một người dân đến được điểm sơ tán. Tuy nhiên mỗi điểm sơ tán lại chỉ có một sức chứa nhất định.

Yêu cầu: Tìm thời gian ngắn nhất cần để sơ tán hết ~n~ người dân.

Input

• Dòng đầu tiên chứa 2 số nguyên ~n,k~ (~n \le 10^5,k \le 20~)

• ~n-1~ dòng sau mỗi dòng chứa 3 số nguyên ~u,v,w~ thể hiện một cạnh của cây (~1 \le u, v \le n, 1 \le w \le 10^9~)

• ~k~ dòng sau mỗi dòng chứa 2 số nguyên ~u, v~ thể hiện một điểm sơ tán và sức chứa của nó (~1 \le u \le n, 1 \le v \le 10^9~). Input đảm bảo ~\Sigma v \ge n~

Output

• Một dòng duy nhất là thời gian ngắn nhất để sơ tán toàn bộ người dân

Sample Input 1

7 3
1 2 5
3 4 5
1 4 1
4 5 7
5 6 2
6 7 1
3 3
7 3
6 2

Sample Output 1

11