Cho một đồ thị vô hướng có ~n~ đỉnh, đỉnh thứ ~i~ có màu ~a_i~. Ban đầu đồ thị chưa có cạnh nào.

Cho ~q~ truy vấn, mỗi truy vấn thuộc một trong hai dạng sau:

• ~1~ ~u~ ~v~: Thêm một cạnh nối ~u~ và ~v~.
• ~2~ ~u~ ~c~: Tính số đỉnh có màu ~c~ trong vùng liên thông của ~u~.

Input:

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~q~ ~(n \le 10^5, q \le 2*10^5)~
• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1,a_2,...,a_n~. ~(a_i \le n)~.
• ~q~ dòng cuối cùng, mỗi dòng gồm ba số nguyên dương, số nguyên đầu tiên là loại của truy vấn (~1~ hoặc ~2~), hai số nguyên dương còn lại không vượt quá ~n~.

Output

• Với mỗi truy vấn loại ~2~, in ra trên một dòng kết quả của truy vấn đó.

Subtask

• Có ~30\%~ số test chứa ~n,q \le 5000~.
• ~70\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

1
0
3
1

Cho một cây vô hướng gồm ~n~ đỉnh và số nguyên dương ~k~.

Đếm các cặp đỉnh ~(u,v)~ ~(u > v)~ sao cho khoảng cách của chúng trên cây bằng ~k~.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~k~ ~(1 \le k \le n \le 10^6)~.
• ~n-1~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~u_i,v_i~ ~(1 \le u_i,v_i \le n u_i \neq v_i;)~.

Output

• In ra một số nguyên không âm là kết quả bài toán.

Ràng buộc

• Có ~25\%~ số test thỏa mãn: ~k \le 50, n \le 1000~.
• Có ~25\%~ số test thỏa mãn: ~k \le 500, n \le 5 \times 10^4~.
• Có ~25\%~ số test thỏa mãn: ~n \le 10^5~.
• Có ~25\%~ số test thỏa mãn: ~n \le 10^6~.

Ví dụ

Input

5 2
1 2
2 3
3 4
2 5

Output

4

Kết hợp với IOI, thành phố Pattaya sẽ tổ chức cuộc đua: Olympic quốc tế về đua tốc độ (IOR) 2011.

Là nhà tổ chức, chúng ta phải tìm ra vòng đua tốt nhất nếu cuộc thi tốc độ này được tổ chức.

Ở vùng Pattaya - Chonburi, có ~N~ thành phố được nối với nhau bởi ~N - 1~ đường cao tốc. Mỗi đường cao tốc đều cho phép đi theo cả hai chiều và nối hai thành phố phân biệt với độ dài đo bởi kilomet là số nguyên. Ngoài ra, có đúng một đường đi giữa mỗi cặp thành phố bất kỳ. Nghĩa là, có đúng một cách đi từ một thành phố này tới một thành phố khác sao cho không đi qua thành phố nào quá một lần (đồ thị là cây).

IOR có quy tắc đặc biệt: đội nào vượt qua vòng đua dài đúng ~K~ kilomet, bắt đầu và kết thúc ở hai thành phố phân biệt, thì sẽ chiến thắng. Rõ ràng là không có đường cao tốc (và vì thế cũng không có thành phố) nào có thể được sử dụng nhiều hơn một lần trên vòng đua để ngăn ngừa ùn tắc. Vòng đua phải chứa một số ít nhất 1 thành phố.

Yêu cầu: Bạn hãy cho biết số lượng đường cao tốc nhỏ nhất trên vòng đua hợp quy tắc có độ dài đúng ~K~. Nếu không tìm được vòng đua như vậy, kết quả sẽ là ~-1~.

Input

Dòng đầu ghi hai số nguyên ~N, K~.

~N - 1~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u, v, l~ - đường cao tốc nối thành phố ~u~ và ~v~, có độ dài ~l~.

Output

Một số nguyên duy nhất - là số lượng đường cao tốc ít nhất tạo thành vòng đua dài đúng ~K~, hoặc ~-1~ nếu không có.

Giới hạn

• ~1 \leq N \leq 2 \times 10^5~

• ~1 \leq K \leq 10^6~

• 1 \leq l \leq 10^6~

Sample Input 1

4 3
0 1 1
1 2 2
1 3 4

Sample Output 1

2

Thành có một cây gồm ~n~ đỉnh, được đánh số từ ~1~ đến ~n~. Mỗi đỉnh ~i~ có trọng số là ~a_i~.

Thành muốn tìm hiểu các vùng liên thông trong cây. Một vùng liên thông được định nghĩa là một tập các đỉnh sao cho giữa hai đỉnh bất kỳ trong tập này luôn tồn tại một đường đi chỉ gồm các đỉnh trong tập đó.

Với mỗi số nguyên ~k~ từ ~1~ đến ~n~, hãy xác định tổng trọng số lớn nhất của một vùng liên thông gồm đúng ~k~ đỉnh.

Input

Dòng đầu tiên chứa số nguyên ~n~ (~1 \leq n \leq 5000~) — số lượng đỉnh của cây.

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~|a_i| \leq 10^4~) — trọng số của các đỉnh.

Mỗi dòng trong ~n-1~ dòng tiếp theo chứa hai số nguyên ~u~ và ~v~ (~1 \leq u, v \leq n~) — biểu diễn một cạnh nối đỉnh ~u~ và ~v~.

Output

In ra ~n~ dòng, dòng thứ ~k~ chứa một số nguyên là tổng trọng số lớn nhất của một vùng liên thông gồm đúng ~k~ đỉnh.

Sample Input 1

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

Sample Output 1

5
8
12
13
15

Giải thích

Với ~k = 1~: chọn đỉnh có trọng số lớn nhất là đỉnh 5 → ~5~

Với ~k = 2~: chọn đỉnh 5 và 3 → ~5 + 3 = 8~

Với ~k = 3~: chọn 3-4-5 → ~3 + 4 + 5 = 12~

Với ~k = 4~: chọn 1-3-4-5 → ~1 + 3 + 4 + 5 = 13~

Với ~k = 5~: toàn bộ cây → ~1 + 2 + 3 + 4 + 5 = 15~

Công ty ABC có ~𝑁~ người. Ngoài giám đốc, mỗi người có duy nhất một cấp trên trực tiếp quản lý. Người ~𝑋~ được gọi là sếp của người ~Y~ nếu ~𝑋~ là cấp trên trực tiếp của ~𝑌~ hoặc ~𝑋~ là sếp của cấp trên trực tiếp của ~𝑌~. Để quảng cáo cho tình hình hoạt động, cũng như điều kiện làm việc tốt của công ty, Giám đốc muốn đưa ra ~𝐾~ người có tổng tiền lương lớn nhất sao cho không có hai người nào trong ~𝐾~ người đó mà người này là sếp người kia.

Yêu cầu: Tính tổng tiền lương lớn nhất của những người đã chọn.

Input

• Dòng đầu là số nguyên ~𝑇 ≤ 100~ - số lượng test trong file dữ liệu. Theo sau là 𝑇 nhóm dòng, mỗi nhóm dòng chứa:
• Dòng đầu chứa hai số nguyên dương 𝑁,𝐾
• Dòng thứ ~𝑖 (1 ≤ 𝑖 ≤ 𝑁)~ trong ~𝑁~ dòng tiếp theo chứa hai số tự nhiên ~𝑝_𝑖, 𝑤_𝑖~ ~(𝑤𝑖 ≤10^3; 𝑝_𝑖 ≤ 𝑁, )~. Với ~𝑝_𝑖~ là cấp trên trực tiếp của người thứ ~𝑖~ (~𝑝_𝑖 = 0~ khi người ~𝑖~ là giám đốc công ty), ~𝑤_𝑖~ là tiền lương người ~𝑖~ nhận được.

Tổng số dòng trong input không vượt quá ~10^5+2~

Subtask

• Subtask ~1~ ~(50\%)~ : ~K \le N \le 10~
• Subtask ~2~ ~(25\%)~ : ~K \le 10, N \le 10^4, T \le 10~
• Subtask ~3~ ~(25\%)~ : ~K \le 10^3, N \le 10^5~

Constraints

• ~1 \le n,q \le 10^5~
• ~1 \le u,v \le n~
• ~1 \le c_i \le 10^5~

Output

• ~𝑇~ dòng tương ứng ước lượng giá trị lớn nhất tiền lương trong ~𝑇~ test theo thứ tự. Nếu không thể chọn đủ ~𝐾~ người thỏa mãn thì đưa ra ~0~.

Sample Input 1

1
6 3
0 9
1 5
2 6
6 1
2 3
1 2

Sample Output 1

11

Bạn được cho một cây (đồ thị liên thông vô hướng không có chu trình) gồm ~n~ nút, gốc tại nút ~1~. Mỗi nút sẽ có một giá trị ~a_i~.

Có ~q~ truy vấn mà bạn cần phải trả lời, mỗi truy vấn có dạng ~u_i~: Xét tích của tất cả các giá trị của các nút trong cây con gốc ~u_i~, bạn cần phải trả lời xem tích đó có bao nhiêu ước.

Chú thích: Do kết quả có thể vượt quá giới hạn dữ liệu, bạn chỉ cần in ra kết quả truy vấn lấy mod ~10^9 + 7~.

Input

• Dòng đầu chứa hai số nguyên ~n~ và ~q~ — số lượng nút của cây và số lượng truy vấn. (~1 \leq n, q \leq 10^5~)

• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ — giá trị tại mỗi nút. (~1 \leq a_i \leq 10^5~)

• ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u_i, v_i~ — biểu thị một cạnh nối giữa nút ~u_i~ và ~v_i~. (~1 \leq u_i, v_i \leq n~)

Dòng cuối chứa ~q~ số nguyên ~u_1, u_2, \dots, u_q~ — là các nút gốc của cây con trong các truy vấn. (~1 \leq u_i \leq n~)

Output

• In ra một dòng gồm ~q~ số nguyên, số thứ ~i~ là kết quả cho truy vấn thứ ~i~.

Ràng buộc

• Có ~50%~ số lượng test thỏa mãn: ~1 \leq n, q \leq 10^3~

• Có ~50%~ số lượng test còn lại: ~1 \leq n, q \leq 10^5~

Sample Input 1

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

Sample Output 1

14 4 6 3 2

Đất nước VNOI là một quốc đảo tuyệt đẹp với dòng nước biển xanh biếc và các bãi cát trắng trải dài vô tận. Đất nước bao gồm ~n~ hòn đảo được kết nối với nhau bởi ~n-1~ cây cầu đảm bảo luôn có đường đi giữa hai hòn đảo bất kì. Nhân mùa du lịch năm ~2023~ chuẩn bị đến, chính phủ VNOI ban hành một chính sách đặc biệt nhằm thu hút khách du lịch: Mỗi du khách khi đến thăm hòn đảo thứ ~i~ sẽ nhận được một phần quà đặc biệt là một kí tự ~c_i~.

Ngay sau khi chính sách được ban hành, đã có hàng loạt du khách đặt vé du lịch đến đất nước VNOI. Chính phủ VNOI tính toán được rằng, sẽ có ~Q~ vị khách du lịch ghé thăm đất nước. Vị khách thứ ~i~ sẽ bắt đầu chuyến thăm quan của mình tại hòn đảo ~u_i~ và anh ta muốn thu thập được các món quà lần lượt được thể hiện qua xâu ~s_i~. Hành trình của vị khách sẽ bắt đầu tại hòn đảo ~u_i~ và đi qua một số hòn đảo sao cho không có hòn đảo nào được đi qua ~2~ lần. Tuy nhiên, do hiện nay đang diễn ra đại chiến ICPC tại hòn đảo thứ ~1~ nên các du khách sẽ muốn hạn chế lại gần hòn đảo này. Vì thế hành trình du lịch của vị khách thứ ~i~ sẽ không được phép đi qua các hòn đảo có khoảng cách đến hòn đảo thứ ~1~ nhỏ hơn khoảng cách từ hòn đảo ~u_i~ đến hòn đảo thứ ~1~.

Yêu cầu: Với mỗi vị khách du lịch hãy giúp chính phủ VNOI tính toán số lượng hành trình du lịch thỏa mãn mong muốn của vị khách ấy nhé!

Input

Vào từ file văn bản str.inp:

• Dòng đầu tiên chứa số ~n~ và ~Q~ cho biết số hòn đảo và số lượng du khách đến thăm đất nước VNOI ~(1 \leq n,Q \leq 2 \cdot 10^5)~.

• Dòng thứ hai chứa ~n~ kí tự ~c_i~ (~c_i~ là một kí tự tiếng Anh in thường) thể hiện các phần quà nhận được khi đến hòn đảo ~i~.

• ~n - 1~ dòng tiếp theo mỗi dòng chứa 2 số ~u~ ~v~ thể hiện có cây cầu kết nối giữa hòn đảo ~u~ và hòn đảo ~v~ ~(1 \leq u,v \leq n)~.

• ~Q~ dòng cuối, dòng thứ ~i~ chứa hòn đảo bắt đầu ~u_i~ và xâu thể hiện dãy các món quà mà vị khách thứ ~i~ muốn thu thập.

Dữ liệu đảm bảo tổng độ dài các xâu ~s_i \leq 5 \cdot 10^5~.

Output

Đưa ra file văn bản str.out ~Q~ dòng:

• Dòng thứ ~i~ thể hiện số lượng hành trình thỏa mãn yêu cầu của vị khách thứ ~i~.

Scoring

Gọi S là tổng độ dài các xâu ~s_i~.

Sample Input 1

10 10
iotmmoomoo
6 8
5 7
9 4
2 4
4 7
10 3
7 1
8 10
8 7
7 omo
7 omo
1 iomo
7 omo
1 iomo
1 iomo
1 iomo
1 iomo
1 iomo
7 omo

Sample Output 1

4
4
4
4
4
4
4
4
4
4