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

Cho có một đồ thị dạng cây gồm ~n~ nút, mỗi nút được đánh số từ 1. Nút ~i~ được tô màu ~a_i~.

Hãy tính tổng tất cả đường đi ngắn nhất giữa hai nút u và v được tô cùng một chung màu. Tổng có thể được biểu diễn như sau:

~\sum dist(u , v)~ ~\forall~ ~u \leq v~ và ~a_u = a_v~.

Trong đó, ~dist(u , v)~ là độ dài đường đi ngắn nhất giữa hay nút ~u~ và ~v~. Độ dài một đường đi từ u đến v được tính bằng tổng số cạnh nằm trên đường đi đó.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ là số đỉnh của cây.

• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_i~ biểu thị một màu của đỉnh ~i~.

• ~n~ dòng tiếp theo, môi dòng chứa ~2~ số nguyên dương ~u~ và ~v~ biểu thị một cạnh nối giữa hai đỉnh ~u~ và ~v~.

Output

• Hãy in ra tổng cần tìm

Scoring

• Subtask ~1~ (~18\%~ số điểm): ~1 \leq n \leq 10~ và ~1 \leq a_i \leq 3*10^5~.

• Subtask ~2~ (~18\%~ số điểm): ~1 \leq n \leq 1000~ và ~1 \leq a_i \leq 3*10^5~.

• Subtask ~3~ (~18\%~ số điểm): ~1 \leq n \leq 3*10^5~ và ~1 \leq a_i \leq 10~.

• Subtask ~4~ (~46\%~ số điểm): ~1 \leq n \leq 3*10^5~ và ~1 \leq a_i \leq 3*10^5~.

Sample Input 1

4
1 3 1 3
1 2
2 3
2 4

Sample Output 1

3

Sample Input 2

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

Sample Output 2

38

Vương quốc Alpha là một tiểu vương quốc mới được thành lập và đang trên đà phát triển. Quốc vương của họ - Aleck - quyết định chia nhỏ vương quốc thành ~n~ tỉnh thành để dễ dàng kiểm soát hơn. Để tiết kiệm chi phí, nhà vua chỉ cho xây dưng ~n - 1~ con đường kết nối giữa ~2~ tỉnh thành khác nhau, tuy nhiên vẫn phải đảm bảo ~2~ tỉnh thành bất kỳ phải đến được với nhau.

Nhà vua đang gấp rút đề cử ra ~n~ người giám sát, mỗi người sẽ có nhiệm vụ giám sát hoạt động của ~1~ tỉnh thành. Hơn nữa, nhà vua muốn gán cấp bậc của mỗi người giám sát là ~1~ chữ cái từ 'A' đến 'Z' biểu thị cho mức độ quan trọng của tỉnh thành đó. Bậc 'A' là cao nhất, còn bậc 'Z' là thấp nhất.

Việc gán cấp bậc cho mỗi người giám sát còn phải đảm bảo được rằng: Nếu tồn tại ~2~ thành phố có người giám sát là cùng bậc, thì đường đi kết nối giữa ~2~ thành phố đó phải đi qua ít nhất ~1~ thành phố có người giám sát có cấp bậc cao hơn. Điều này cho thấy được tầm quan trọng của những người giám sát bậc cao.

Đề xuất cho nhà vua Aleck ~1~ cách để thực hiện việc đó, hoặc thông báo cho nhà vua biết điều đó là bất khả thi.

Input

Dòng ~1~: Gồm một số nguyên ~n~ ~(1 \le n \le 10^5)~ là số lượng tỉnh thành của vương quốc Alpha.

~n - 1~ dòng tiếp theo, mỗi dòng chứa ~2~ số nguyên ~a, b~ ~(1 \le a, b \le n; a \ne b)~ là một con đường ~2~ chiều kết nối giữa ~2~ tỉnh thành ~a~ và ~b~.

Output

Nếu có ~1~ cách thỏa mãn, in ra ~n~ chữ cái in hoa, chữ cái thứ ~i~ đại diện cho cấp bậc của người giám sát cho tỉnh thành ~i~.

Nếu không, in ra 'Impossible!'.

Scoring

Subtask ~1~ ~(30\%~ số điểm~):~ Mỗi tỉnh thành chỉ được kết nối với tối đa ~2~ tỉnh thành khác.

Subtask ~2~:~(30\%~ số điểm~):~ Khoảng cách tối đa giữa ~2~ tỉnh thành bất kỳ không vượt quá ~50~.

Subtask ~3~:~(40\%~ số điểm~):~ Không có điều kiện gì thêm.

Sample Input 1

4
1 2
1 3
1 4

Sample Output 1

A B B B

Sample Input 2

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

Sample Output 2

D C B C A D C B C D

Vương quốc có ~n~ thành phố và ~n-1~ con đường hai chiều, đảm bảo đi lại giữa mọi cặp thành phố. Thành phố x được gọi là quản lý ~y~ nếu ~x~ nằm trên đường đi đơn từ ~y~ đến 1. Sản lượng lương thực tại thành phố ~x~ là ~w_x~. Quốc vương muốn chọn ra một đỉnh để xây dựng kho dự trữ, chi phí vận chuyển lương thực nếu xây dựng kho dự trữ tại ~u~ là ~∑_{v=1}^n {w_v×d(v,u)}~ với ~d(v,u)~ là số cạnh trên đường đi đơn từ ~v~ đến ~u~.

Có ~Q~ thay đổi cho sản lượng được báo cáo, mỗi thay đổi có dạng ~1\ u\ c~ hoặc ~2\ u\ c~ tương ứng là tăng ~w_u~ lên ~c~ đơn vị hoặc tăng ~w_v~ lên ~c~ đơn vị với mọi ~v~ quản lý bởi ~u~. Sau mỗi thay đổi, cần tìm đỉnh ~u~ để xây dựng kho dữ trữ sao cho tổng chi phí vận chuyển lương thực là nhỏ nhất, nếu có nhiều ~u~ như vậy thì chọn ~u~ nhỏ nhất.

Input

• Dòng đầu chứa hai số nguyên dương ~n~ và ~Q~;
• Dòng thứ hai chứa ~n~ số ~w_1,w_2,...,w_n~;
• Mỗi dòng trong số ~n - 1~ dòng tiếp theo chứa hai số ~u\ v~ mô tả một cạnh của cây;
• Mỗi dòng trong số ~Q~ dòng tiếp theo chứa ba số ~t\ u\ c~ mô tả một thay đổi

Output

• Ghi ~Q~ dòng là chỉ số của đỉnh được chọn sau thay đổi thứ ~Q~.

Scoring

• Trong tất cả các test: ~n,Q ≤ 10^5; 1 ≤ w_i ≤ 10^6; |c| ≤ 10^6.~
• Có 12% số test với ~n,Q ≤ 5000~;
• Có 16% số test có cạnh nối từ ~x~ đến ~x - 1~ với mọi ~2 ≤ x ≤ n;~
• Có 16% số test có cạnh nối từ ~x~ đến ~[x/2]~ với mọi ~2 ≤ x ≤ n;~
• Có 20% số test không có thay đổi loại 2;
• Có 36% số test với ràng buộc gốc. uộc gốc

Sample Input 1

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

Sample Output 1

2 
2 
1

Để kỉ niệm Tết, thành phố quyết định bắt pháo hoa. tổng cộng ~n~ địa điểm bắn pháo hoa và các địa điểm này được nối với nhau bằng ~n - 1~ con đường hai chiều sao cho giữa hai địa điểm bất kỳ có đúng một đường đi từ địa điểm này sang địa điểm kia. Độ dài mỗi đường đi là số lượng cạnh trên đường đi đó. Ban tổ chức đánh giá độ đẹp và độ ảnh hưởng của các loại pháo hoa như sau:

• Một loại pháo hoa được gọi là có giới hạn ảnh hưởng ~s~ thì nó chỉ ảnh hưởng đến những người dân đứng tại các địa điểm có độ dài quãng đường đến địa điểm bắn loại pháo hoa đó nhỏ hơn hoặc bằng ~s~.
• Một loại pháo hoa được gọi là có giá trị độ đẹp ~c~ thì người dân đứng tại các địa điểm trong giới hạn ảnh hưởng của loại pháo hoa này được hưởng trọn vẹn độ đẹp ~c~.

Có tổng cộng ~m~ loại pháo hoa được bắn. Loại pháo hoa thứ ~i~ (~1 \leq i \leq m~) có độ đẹp mắt ~c_{i}~, độ ảnh hưởng ~s_{i}~, và sẽ được bắn liên tục ở địa điểm ~u_{i}~ kể từ giây thứ ~t_{i}~ tính từ thời khắc giao thừa.

Yêu cầu: Bạn cần trả lời ~q~ câu hỏi, câu hỏi thứ ~j~ (~1 \leq j \leq q~) yêu cầu tính tổng độ đẹp mắt của các pháo hoa trong giới hạn ảnh hưởng đến người dân đứng ở địa điểm thứ ~v_{j}~ ngay sau giây thứ ~d_{j}~ tính từ giao thừa.

Input

• Dòng đầu tiên chứa ba số nguyên dương ~n, m, q~ (~1 \leq n, m, q \leq 10^{5}~) lần lượt là số địa điểm bắn pháo hoa, số loại pháo hoa và số câu hỏi.
• Dòng thứ ~i~ trong số ~n - 1~ dòng tiếp theo chứa hai số nguyên dương ~a_{i}~ và ~b_{i}~ (~1 \leq a_{i}, b_{i} \leq n~) thể hiện rằng có con đường hai chiều giữa địa điểm ~a_{i}~ và ~b_{i}~.
• Dòng thứ ~i~ trong số ~m~ dòng tiếp theo chứa ba số nguyên ~t_{i}, u_{i}, c_{i}, s_{i}~ (~0 \leq t_{i}, c_{i} \leq 10^{7}, 1 \leq u_{i} \leq n, 0 \leq s_{i} < n~) lần lượt là thời điểm loại pháo hoa thứ ~i~ bắt đầu bắn, địa điểm được bắn, độ đẹp mắt và giới hạn ảnh hưởng của loại pháo hoa đó.
• Dòng thứ ~j~ trong số ~q~ dòng tiếp theo chứa hai số nguyên ~d_{j}~ và ~v_{j}~ (~0 \leq d_{j} \leq 10^{7}, 1 \leq v_{j} \leq n~) là nội dung câu hỏi thứ ~j~.

Output

• Ghi ra ~q~ dòng, dòng thứ ~i~ ghi một số nguyên duy nhất là câu trả lời cho câu hỏi thứ ~i~.

Scoring

• Subtask ~1~ (~15\%~ số điểm): ~n, m, q \leq 500~.
• Subtask ~2~ (~15\%~ số điểm): ~n, m, q \leq 5 \times 10^{3}~.
• Subtask ~3~ (~15\%~ số điểm): ~a_{i} = i, b_{i} = i + 1, \forall 1 \leq i < n~.
• Subtask ~4~ (~20\%~ số điểm): ~s_{i} = 1, \forall 1 \leq i \leq m~.
• Subtask ~5~ (~20\%~ số điểm): ~s_{i} = 2, \forall 1 \leq i \leq m~.
• Subtask ~6~ (~15\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

20 
20 
0 
10 
30 
0 
30