Cho một đồ thị gồm ~n~ đỉnh và ~m~ cạnh có hướng có trọng số.

Với mỗi đỉnh ~i~, hãy tính độ dài của quãng đường ngắn nhất để đi xuất phát từ đỉnh ~1~, đi qua đỉnh ~i~ và quay về đỉnh ~1~.

Input

• Dòng thứ nhất chứa ~2~ số nguyên dương ~n,m~.
• ~m~ dòng sau mỗi dòng gồm ~3~ số nguyên dương ~u,v,w~ ~(1 \le u, v \le n, u \neq v)~, miêu tả cạnh gồm đỉnh ~u~ nối với đỉnh ~v~ có trọng số ~w~.

Output

• Gồm ~n~ dòng, dòng thứ ~i~ in ra độ dài của quãng đường ngắn nhất để đi xuất phát từ đỉnh ~1~, đi qua đỉnh ~i~ và quay về đỉnh ~1~. Nếu không có quãng đường nào như vậy thì in ra ~-1~.

Constraints

• ~1 \le n,n \le 2*10^5~.
• ~1 \le w \le 10^9~.

Subtasks

• Subtask ~1~: Nếu tồn tại cạnh ~(u,v,w)~ thì sẽ có cạnh ~(v,u,w)~. ~(30\%)~
• Subtask ~2~: Không có ràng buộc gì thêm ~(70\%)~

Sample Input 1:

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

Sample Output 1:

-1
-1
-1
10

Sample Input 2:

2 1
2 1 10

Sample Output 2:

-1

Có ~n~ điểm từ ~1~ tới ~n~ trên trục tọa độ ~OX~. Điểm thứ ~i~ có màu ~c_i~.

Tại điểm ~i~, bạn có thể:

• Đi tới điểm ~i+1~ (nếu ~i \neq n~), tốn ~R~ giây.
• Đi tới điểm ~i-1~ (nếu ~i \neq 1~), tốn ~L~ giây.
• Tốc biến tới điểm ~j~ (nếu ~c_i = c_j~), tốn ~C~ giây.

Cho ~2~ điểm ~st~ và ~en~, hãy tính thời gian ngắn nhất để đi từ ~st~ đến ~en~.

Input

• Dòng thứ nhất chứa ~4~ số nguyên dương ~n,L,R,C~.
• Dòng thứ hai gồm ~2~ số nguyên dương ~st~ và ~en~. ~(1 \le st \le en \le n)~
• Dòng thứ ba chứa ~N~ số nguyên dương ~c_1, c_2, ..., c_n~ là màu của từng điểm.

Output

• In ra thời gian ngắn nhất để đi từ ~st~ đến ~en~.

Constraints

• ~1 \le n \le 10^5~.
• ~1 \le L,R,C \le 10^9~.
• ~1 \le c_i \le 10^5~.

Sample Input 1:

5 1 2 3
1 5
1 2 1 1 2

Sample Output 1:

5

Sample Input 1:

5 1 4 3
3 5
1 2 1 1 2

Sample Output 1:

4

Subtasks

• Subtask ~1~: ~n \le 1000~ ~(50\%)~
• Subtask ~2~: Không có ràng buộc gì thêm ~(50\%)~

Đất nước ~ABC~ có ~n~ thành phố và ~m~ con đường một chiều. Con đường thứ ~i~ nối hai thành phố ~u_i~ và ~v_i~ với nhau, có độ dài ~l_i~ và có chi phí ~t_i~.

~H~ là một du khách. Hiện tại, anh đang ở thành phố ~1~ và cần đi tới thành phố ~n~. Tuy nhiên anh ta chỉ mang đúng ~K~ đồng tiền.

Hãy giúp ~H~ tính toán lộ trình ngắn nhất từ thành phố ~1~ tới ~n~ mà chỉ mất tổng chi phí ít hơn hoặc bằng ~K~.

Input

• Dòng thứ nhất chứa ~2~ số nguyên dương ~n,m~.
• Dòng thứ hai chứa số nguyên dương ~K~.
• ~m~ dòng sau mỗi dòng gồm ~4~ số nguyên dương ~u_i,v_i,l_i,t_i~ ~(1 \le u, v \le n, u \neq v)~, miêu tả con đường nối thành phố ~u_i~ với ~v_i~ có độ dài ~l_i~ và chi phí ~t_i~.

Output

• In ra độ dài đường đi ngắn nhất từ ~1~ tới ~n~ mà tổng chi phí không quá ~K~.
• Nếu không có lộ trình nào để đi từ ~1~ tới ~n~ và tiêu không quá ~K~, in ra ~-1~.

Constraints

• ~1 \le n \le 100~.
• ~1 \le m \le 1000~.
• ~1 \le k \le 10000~.
• ~1 \le l_i \le 1000~.
• ~0 \le t_i \le 1000~.

Subtasks

• Subtask ~1~: ~1 \le n,m \le 20~ ~(30\%)~
• Subtask ~2~: Không có ràng buộc gì thêm ~(70\%)~

Sample Input 1:

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

Sample Output 1:

11

Explanation 1:

Đi theo lộ trình ~(1,3,5,4,6)~.

Sample Input 2:

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

Sample Output 2:

-1

Explanation 2:

Không có lộ trình nào để đi từ ~1~ tới ~4~ tiêu không quá ~0~.

Đất nước ~ABC~ có ~n~ thành phố và ~m~ con đường hai chiều. Con đường thứ ~i~ nối hai thành phố ~u_i~ và ~v_i~ với nhau, có độ dài ~l_i~ và độ đẹp ~b_i~.

~H~ là một du khách. Hiện tại, anh đang ở thành phố ~1~ và cần đi tới thành phố ~n~ để dự sự kiện. Là một người đam mê cái đẹp, anh muốn chọn một lộ trình sao cho những con đường anh đi qua có tổng độ đẹp là lớn nhất, tuy vậy do cần tiết kiệm thời gian nên anh sẽ chỉ chọn lộ trình ngắn nhất (tức là tổng độ dài các con đường là bé nhất có thể) để đi từ ~1~ tới ~n~.

Hãy giúp ~H~ tính toán lộ trình ngắn nhất và có tổng độ đẹp lớn nhất mà anh ta có thể đi.

Input

• Dòng thứ nhất chứa ~2~ số nguyên dương ~n,m~.
• ~m~ dòng sau mỗi dòng gồm ~4~ số nguyên dương ~u_i,v_i,l_i,c_i~ ~(1 \le u, v \le n, u \neq v)~, miêu tả con đường nối thành phố ~u_i~ với ~v_i~ có độ dài ~l_i~ và độ đẹp ~c_i~.

Output

• Gồm một dòng chứa hai số nguyên ~L~ và ~B~, với ~L~ là độ dài của lộ trình ngắn nhất để đi từ ~1~ tới ~n~ và ~B~ là độ đẹp lớn nhất có thể của các lộ trình có độ dài ~L~.
• Nếu không có lộ trình nào để đi từ ~1~ tới ~n~, in ra ~-1~.

Constraints

• ~1 \le n,m \le 2*10^5~.
• ~1 \le l_i,c_i \le 10^9~.

Subtasks

• Subtask ~1~: ~1 \le n,m \le 20~ ~(30\%)~
• Subtask ~2~: Không có ràng buộc gì thêm ~(70\%)~

Sample Input 1:

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

Sample Output 1:

6 7

Explanation 1:

Có hai lộ trình có độ dài ~6~ có thể đi là ~(1,2,5)~ và ~(1,3,4,5)~. Trong đó lộ trình ~(1,3,4,5)~ có độ đẹp lớn nhất là bằng ~7~.

Sample Input 2:

4 2
1 2 1 1
1 3 1 1

Sample Output 2:

-1

Explanation 2:

Không có lộ trình nào để đi từ ~1~ tới ~4~.

Hành tinh Marvelous Land gồm ~N~ thành phố, được kết nối với nhau bởi ~M~ tuyến đường hai chiều. Giữa hai thành phố chỉ có tối đa một tuyến đường nối chúng và không có tuyến đường nào nối một thành phố tới chính nó. Các thành phố được đánh số từ 1 tới ~N~. Trong đó có 2 thành phố là trung tâm kinh tế quan trọng là thành phố 1 và thành phố ~N~. Tuyến đường thứ ~i~ cho phép đi lại giữa hai thành phố ~u_i~ và ~v_i~ với ~t_i~ đơn vị thời gian. Một ngày nọ, người dân Marvelous Land khảo sát các con đường và nhận thấy cần nâng cấp mạng lưới đường hiện có, hoặc xây thêm một số tuyến đường hai chiều. Điều cần quan tâm nhất là tổng thời gian ngắn nhất để đi lại giữa 2 thành phố trung tâm kinh tế. Trước khi quyết định nâng cấp mạng lưới đường đi, cần xác định các tuyến đường trọng yếu là những tuyến đường mà không thể không đi qua khi muốn đi từ thành phố 1 tới thành phố ~N~ với tổng thời gian ngắn nhất.

Yêu cầu: Hãy viết chương trình đếm số lượng tuyến đường trọng yếu.

Input

• Dòng đầu chứa hai số nguyên ~N~ và ~M~ (~1 \le N \le 10^5, 1 \le M \le 2 × 10^5~), số thành phố và số tuyến đường.
• ~M~ dòng tiếp theo, mỗi dòng ghi ba số nguyên, dòng thứ ~i+1~ ghi số ~u_i, v_i, t_i~ (~1 \le u_i, v_i \le N, 1 \le t_i \le 10^6~) là các thông tin của tuyến đường thứ ~i~.

Output

• Ghi ra duy nhất một số nguyên là số tuyến đường trọng yếu.

Subtask

• 50% số điểm của bài tương ứng với các test có ~N \le 1000~ và ~M \le 1000~

Sample Input 1

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

Sample Output 1

3

Cho bảng số ~A~ kích thước ~n*m~, các hàng được đánh số từ trên xuống dưới, các cột được đánh số từ trái sang phải. Ô giao giữa hàng ~i~ cột ~j~ là ô ~(i,j)~ và có giá trị ~a(i,j)~. Hai ô có thể di chuyển tới nhau nếu chúng chung cạnh. Một đường đi sẽ bao gồm các ô sao cho hai ô liên tiếp chung cạnh, và nó có giá trị bằng tổng giá trị các ô trên đường đi.

Cho ~q~ truy vấn, truy vấn thứ ~i~ sẽ cho bạn hai ô ~(x,y)~ và ~(u,v)~ trong bảng. Kết quả của một truy vấn chính là giá trị của đường đi có trọng số nhỏ nhất giữa hai ô đã cho. Hãy in ra kết quả của từng truy vấn.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,m~, ~(1 \le n \le 7; 1 \le m \le 5000)~.
• Tiếp theo là ~n~ dòng, mỗi dòng gồm ~m~ số nguyên không âm miêu tả bảng ~A~ ~n*m~, ~(0 \le a(i,j) \le 10^5)~ .
• Dòng tiếp theo là số nguyên dương ~q~, ~(q \le 30000)~.
• Ở ~q~ dòng tiếp theo mỗi dòng miêu tả một truy vấn, truy vấn thứ ~i~ có dạng ~x_i, y_i, u_i, v_i~ miêu tả ô ~(x_i,y_i)~ và ~(u_i,v_i)~. (Các ô đều nằm trong bảng).

Output

• In ra ~q~ dòng là kết quả của ~q~ truy vấn.

Sample Test

Input:

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

Output:

5
9

Cho một đồ thị vô hướng liên thông có trọng số ~n~ đỉnh, ~m~ cạnh. Cạnh thứ ~i~ có trọng số là ~weight(i)~. Định nghĩa cost của 1 đường đi qua các cạnh ~e_1, e_2, ..., e_k~ là:

~k \times X + \sum_{i=1}^{k} weight(e_i) - max(weight(e_1), ..., weight(e_k)) + min(weight(e_1), ..., weight(e_k))~.

Tìm đường đi có cost nhỏ nhất từ ~S~ đến ~n - 1~ đỉnh còn lại.

Input

• Dòng đầu tiên ~4~ số nguyên ~n, m, S, X~ ~(1 \le n, m \le 2 \times 10^5, 1 \le S \le n, 1 \le X \le 10^9)~.

• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa ~3~ số nguyên ~u,v,w~ lần lượt là hai đỉnh và trọng số của cạnh thứ ~i~ ~(1 \le u, v \le n, u \ne v, 1 \le w \le 10^9)~.

Output

• In ra ~n - 1~ số nguyên là kết quả cần tìm. Các khoảng cách được in theo thứ tự đỉnh tăng dần.

Subtask

• ~20\%~ số test có ~1 \le n, m \le 10~.

• ~20\%~ số test khác có ~1 \le n, m \le 100~.

• ~20\%~ số test khác có ~m = n~.

• ~40\%~ số test còn lại không có điều kiện gì thêm.

Sample Input 1

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

Sample Output 1

7 9 7

Cho đồ thị vô hướng không trọng số gồm ~n~ đỉnh và ~m~ cạnh, mỗi cạnh được gán một số nguyên thể hiện "độ đẹp" của cạnh. Alice được thầy dạy về bài toán tìm đường đi ngắn nhất từ đỉnh ~1~ đến đỉnh ~n~. Sau một hồi suy ngẫm, Alice sẽ chọn ra đường đi ngắn nhất có độ chênh lệch giữa độ đẹp lớn nhất và độ đẹp nhỏ nhất là lớn nhất có thể.

Input

• Dòng đầu chứa hai số nguyên ~n, m~ ~(n \le 10^5, m \le 2\times 10^5)~.
• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~u_i,v_i,c_i~ ~(1 \le u_i,v_i \le n, 0 \le c_i \le 10^9)~ thể hiện cạnh nối hai đỉnh ~u_i~ và ~v_i~ có độ đẹp là ~c_i~.

Output

• In ra một số nguyên là độ chênh lệch lớn nhất tìm được.

Sample Input 1

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

Sample Output 1

6

Cho đồ thị đầy đủ vô hướng có trọng số (nghĩa là đồ thị gồm ~\frac{n*(n-1)}{2}~ cạnh phân biệt), trong đó có ~m~ cạnh có trọng số là ~1~, các cạnh còn lại có trọng số là ~0~.

Hãy tìm cây khung nhỏ nhất của đồ thị này.

Input:

• Dòng đầu tiên ghi số nguyên ~n~ và ~m~ ~(1 \le n \le 2*10^5, 1 \le m \le min(4*10^5,\frac{n*(n-1)}{2}))~
• ~m~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên ~u_i,v_i~ ~(1 \le u_i, v_i \le n, u_i \neq v_i)~ - miêu tả cạnh ~(u_i,v_i)~ có trọng số là ~1~.

Output:

• Trọng số của cây khung nhỏ nhất của đồ thị.

Constraints:

• Có ~50\%~ số test ứng với ~n \le 2*10^3~
• ~50\%~ số test còn lại không có điều kiện gì thêm.

Ví dụ

Input 1

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

Output 1

2

Input 2

3 0

Output 2

0

Cho đồ thị vô hướng có trọng số gồm ~n~ đỉnh và ~m~ cạnh không chứa khuyên.

Với mỗi cạnh ~(u,v)~ được cho, hãy tìm trọng số nhỏ nhất có thể của cây khung chứa cạnh ~(u,v)~. Nói cách khác, ta cần tìm trọng số của cây khung nhỏ nhất chứa cạnh ~(u,v)~.

Trọng số cây khung bằng tổng trọng số của tất cả các cạnh trong cây khung.

Input:

• Dòng đầu tiên ghi số nguyên ~n~ và ~m~ ~(1 \le n \le 2*10^5, n-1 \le m \le 2*10^5)~
• ~m~ dòng tiếp theo, mỗi dòng gồm ~3~ số nguyên ~u_i,v_i,w_i~ ~(1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le w_i \le 10^9)~ - lần lượt là hai đỉnh và trọng số của cạnh thứ ~i~.

Output:

• In ra ~m~ dòng, dòng thứ ~i~ chứa trọng số cạnh của cây khung thứ ~i~.

Constraints:

• Có ~50\%~ số test ứng với ~n,m \le 2*10^3~;
• ~50\%~ số test còn lại không có điều kiện gì thêm.

Ví dụ

Input

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

Output

9
8
11
8
8
8
9

Cho đồ thị vô hướng có trọng số gồm ~n~ đỉnh, đồng thời có thêm ~m~ truy vấn có một trong hai dạng như sau:

• ~1~ ~u~ ~v~ thêm cạnh ~(u,v)~ vào đồ thị.
• ~2~ ~u~ ~v~ in ra thời gian sớm nhất (chỉ số của truy vấn) để ~u~ và ~v~ liên thông.

Input:

• Dòng đầu tiên ghi số nguyên ~n~ và ~m~ ~(1 \le n \le 2*10^5; 1 \le m \le 5*10^5)~
• ~m~ dòng tiếp theo, mỗi dòng gồm ~3~ số nguyên ~t,u,v~, nếu ~t = 1~ thì là dạng truy vấn thứ nhất, ngược lại là dạng thứ hai.

Output:

• Với mỗi truy vấn loại ~2~, in ra kết quả. Nếu hai đỉnh chưa liên thông, in ra ~-1~.

Constraints:

• Có ~50\%~ số test ứng với ~n,m \le 2*10^3~;
• ~50\%~ số test còn lại không có điều kiện gì thêm.

Ví dụ

Input

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

Output

1
3
-1

Mùa tuyển sinh đã đến, là một người đã cố gắng suốt cả năm qua nên AP đang phải đau đầu để chọn trường cho mình. Ting ting tiếng chuông điện thoại của AP kêu lên và AP nhận được một tin nhắn từ Hogwarts báo nhập học, AP đồng ý ngay. Đời không như mơ, để bước vào ngôi trường pháp thuật trứ danh này AP phải qua một bài kiểm tra của thầy hiệu trưởng như sau:

AP được phù phép dịch chuyển đến một mỏm đá, trước mặt AP là những hòn đảo được đánh số từ ~1~ đến ~n~ có diện tích là ~w_i~, giữa những hòn đảo có ~m~ cây cầu được xây sắn bằng phép thuật, cây cầu thứ ~j~ nối hai đảo ~u_i~ và ~v_j~ lại với nhau. Thầy hiệu trưởng muốn qua bài thi này để đánh giá khả năng sử dụng thần chú của AP với đề bài là hai thần chú:

• ~C~ ~i~ ~W~ có tác dụng thay đổi kích thước của hòn đảo thứ ~i~ thành diện tích ~W~
• ~D~ ~j~ có tác dụng xóa đi cầy cầu thứ ~j~ (nếu lúc này nó vẫn tồn tại) nối hai hòn đảo ~u_i~ và ~v_j~.

Sau mỗi thao tác thay đổi như thế, thầy hiệu trưởng muốn biết tổng diện tích lớn nhất của những hòn đảo đến được với nhau. Vốn trí nhớ AP không được tốt và AP cũng khá lười để trả lời những câu hỏi của thầy khi thực hiện một đống phép thuật nên AP cần bạn hơn bao giờ hết. Hãy giúp AP trả lời câu hỏi của thầy hiệu trưởng để vượt qua bài kiểm tra nha.

Input:

• Dòng thứ nhất gồm ~3~ số nguyên ~n,m,q~ ~(n,m,q \le 3*10^5)~
• Dòng thứ hai cho biết diện tích ban đầu của ~n~ hòn đảo lần lượt là ~w_1,w_2,...,w_n~ ~(w_i \le 10^9)~
• ~m~ dòng tiếp theo cho biết thứ tự và thông tin các cây cầu được xây sẵn, cây cầu thứ ~j~ nối giữa hai hòn đảo là ~u_i~ và ~v_j~.
• ~q~ dòng tiếp theo cho biết thầy hiệu trưởng yêu cầu AP sử dụng thần chú ~C~ ~i~ ~W~ hoặc ~D~ ~j~.

Output

• ~q~ dòng được in ra là câu trả lời cho yêu cầu của thầy hiệu trưởng, vì thầy hiệu trưởng là một người thông thái cho nên khi đặt câu hỏi cho AP thì luôn có câu trả lời cho câu hỏi đó.

Subtask

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

Sample Input 1

6 6 8
8 2 1 8 3 7 
4 3
4 2
3 4
6 1
4 3
4 3
D 5
D 4
C 5 8
D 3
C 2 8
C 5 1
C 6 1
D 2

Sample Output 1

15
11
11
11
17
17
17
9

Cho đồ thị vô hướng có trọng số gồm ~n~ đỉnh và ~m~ cạnh không chứa khuyên, mỗi cạnh có dạng ~(u,v,c)~, tức là cạnh nối hai đỉnh ~u~ và ~v~ có trọng số ~c~. Lưu ý, không tồn tại quá 5 cạnh có cùng trọng số là ~c~.

Hãy đếm số cây khung nhỏ nhất của đồ thị này. Nói cách khác, đếm số cách giữ lại ít cạnh nhất của đồ thị sao cho đồ thị vẫn liên thông và tổng trọng số các cạnh giữ lại là nhỏ nhất.

Do kết quả có thể rất lớn, hãy in ra đáp số theo modulo ~998244353~.

Input:

• Dòng đầu tiên ghi số nguyên ~n~ và ~m~ ~(1 \le n \le 2*10^5, n-1 \le m \le 2*10^5)~
• ~m~ dòng tiếp theo, mỗi dòng gồm ~3~ số nguyên ~u_i,v_i,w_i~ ~(1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le w_i \le 10^9)~ - lần lượt là hai đỉnh và trọng số của cạnh thứ ~i~.
• Dữ liệu đảm bảo đồ thị liên thông.

Output:

• Gồm một số nguyên duy nhất là số cây khung nhỏ nhất của đồ thị modulo ~998244353~.

Constraints:

• Có ~10\%~ số test ứng với ~m \le 7~
• Có ~20\%~ số test ứng với ~m \le 25~
• Có ~30\%~ số test ứng với ~n = m~;
• ~40\%~ số test còn lại không có điều kiện gì thêm.

Ví dụ

Input 1

3 3
1 2 1
2 3 1
3 1 1

Output 1

3

Input 2

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

Output 2

2

Input 3

4 9
1 2 1
1 2 1
2 3 2
2 3 2
2 3 2
3 4 3
3 4 3
3 4 3
3 4 3

Output 3

24

Cho đồ thị vô hướng có trọng số gồm ~n~ đỉnh và ~m~ cạnh không chứa khuyên, mỗi cạnh có dạng ~(u,v,c)~, tức là cạnh nối hai đỉnh ~u~ và ~v~ có trọng số ~c~.

Với mỗi cạnh, hãy xác định xem cạnh đó có nằm trong mọi cây khung nhỏ nhất của đồ thị hay không.

Input:

• Dòng đầu tiên ghi số nguyên ~n~ và ~m~ ~(1 \le n \le 2*10^5, n-1 \le m \le 2*10^5)~
• ~m~ dòng tiếp theo, mỗi dòng gồm ~3~ số nguyên ~u_i,v_i,w_i~ ~(1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le w_i \le 10^9)~ - lần lượt là hai đỉnh và trọng số của cạnh thứ ~i~.
• Dữ liệu đảm bảo đồ thị liên thông.

Output:

• In ra ~m~ xâu kí tự, trong đó xâu thứ ~i~ là "Yes" nếu cạnh thứ ~i~ thuộc toàn bộ các cây khung nhỏ nhất của đồ thị, "No" nếu ngược lại.

Constraints:

• Có ~10\%~ số test ứng với ~m \le 20~
• Có ~20\%~ số test ứng với ~m \le 300~
• Có ~20\%~ số test ứng với ~m \le 4000~;
• Có ~20\%~ số test ứng với trọng số của mọi cạnh phân biệt.
• ~30\%~ số test còn lại không có điều kiện gì thêm.

Ví dụ

Input 1

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

Output 1

Yes Yes No Yes No No No 

Cho cây ~n~ đỉnh gồm ~n-1~ cạnh có gốc tại đỉnh ~1~. Đỉnh thứ ~i~ có giá trị là ~a_i~.

Đối với mỗi đỉnh ~u~, ta cần phải tính độ đẹp của đường đi xuất phát từ gốc là đỉnh ~1~ tới ~u~. Độ đẹp trên đường đi này được tính như sau:

• Ta có thể chọn tối đa một đỉnh ~v~ bất kì thuộc đường đi từ ~1~ tới ~u~, sau đó gán giá trị ~a_v = 0~.
• Tiếp theo, tính giá trị ~X =~ ước chung lớn nhất theo giá trị của các đỉnh thuộc đường đi từ ~1~ tới ~u~.
• Độ đẹp của đường đi từ ~1~ tới ~u~ là cách thay đỉnh tốt nhất (hoặc có thể giữ nguyên giá trị các đỉnh) sao cho giá trị ~X~ thu được là lớn nhất.

Với mỗi ~u~ từ ~1~ tới ~n~, bạn cần tính được độ đẹp của đường đi ~(1,u)~, lưu ý các truy vấn ở đây là độc lập, nghĩa là bạn không thay đổi thực sự một giá trị nào cả.

Input

• Dòng đầu chứa số nguyên ~n~ ~( n \le 2 \times 10^5)~.
• Dòng tiếp theo gồm ~n~ số nguyên dương miêu tả dãy ~a~ ~(1 \le a_i \le 2 \times 10^5)~
• ~n-1~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~u_i, v_i~ ~(1≤u,v≤n; u≠v;)~ mô tả một cạnh của cây nối hai đỉnh ~u_i~ và ~v_i~.

Output

• In ra ~n~ số nguyên dương là độ đẹp của đường đi ~(1,u)~ với ~u \in [1,n]~

Subtask

• Subtask ~1~: ~n \le 2000 ~. ~(50\%)~
• Subtask ~2~: Không có giới hạn gì thêm. ~(50\%)~

Sample Input 1

3
6 2 3
1 2
1 3

Sample Output 1

6 6 6

Một mê cung được biểu diễn bằng một bảng vuông ~A~ kích thước ~n \times n~ ô, các hàng được đánh số từ ~1~ đến ~n~ từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~n~ từ trái sang phải, ô nằm giao giữa hàng ~i~ và cột ~j~ được gọi là ô ~(i, j)~. Một số ô của bảng có chướng ngại vật và được đánh dấu là ~1~, những ô còn lại là các ô trống và được đánh dấu ~0~. Một robot chỉ di chuyển trong bảng và có thể đi từ ô trống này sang ô trống khác lân cận kề cạnh. Một đường đi của robot giữa hai ô trống là một dãy các ô lân cận từ ô này tới ô kia và không có ô nào đi qua quá một lần, độ dài của đường đi được tính bằng số lượng ô mà robot đi qua. Bảng ~A~ là mê cung nên giữa hai ô trống bất kỳ của bảng có đúng một đường đi giữa chúng.

Hãy xử lí ~q~ thao tác, mỗi thao tác thuộc một trong hai dạng sau:

• Thao tác dạng: ~1~ ~u~ ~v~, thao tác này sẽ thực hiện đặt chướng ngại vật vào ô ~(u, v)~. Chú ý rằng, sau khi thực hiện thao tác loại này, bảng ~A~ có thể không còn là mê cung nữa;
• Thao tác dạng: ~2~ ~u~ ~v~ ~x~ ~y~, thao tác này cần tính độ dài đường đi từ ô ~(u, v)~ đến ô ~(x, y)~. Nếu không tồn tại đường đi đưa ra ~-1~.

Input: nhập vào từ file "KPMC.INP"

• Dòng đầu tiên chứa hai số nguyên dương ~n,q~.
• Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa xâu ~n~ kí tự ~[0,1]~ mô tả hàng ~i~ của ~A~.
• Dòng thứ ~j~ trong ~q~ dòng tiếp theo mô tả thao tác thứ ~j~.

Output: ghi ra file "KPMC.OUT"

• Gồm một số dòng tương ứng là các câu trả lời cho thao tác tìm độ dài đường đi giữa hai ô.

Subtask

• Subtask ~1~ ~(30\%)~: ~n,q \le 100~.
• Subtask ~2~ ~(30\%)~: ~n \le 1000~ và chỉ có thao tác loại ~2~.
• Subtask ~3~ ~(40\%)~: ~n \le 1000, q \le 10^5~.

Ví dụ

Sample Input 1

3 3
000
110
000
2 1 1 3 1
1 2 3
2 1 1 3 1

Sample Output 1

7
-1

Tâm và Gia Huy đang trong quá trình luyện tập cho kì thi ICPC WF sắp tới.

Trường đại học nơi Tâm và Gia Huy đang theo học là một tập hợp các phòng học gồm ~n~ phòng được kết nối bởi ~n-1~ hành lang và được đảm bảo có thể đi từ bất kì phòng học này đến phòng học khác. Các phòng được đánh số từ ~1~ đến ~n~.

Vào mỗi ngày họ sẽ luyện tập riêng lẻ ở trong các phòng học khác nhau, và sau mỗi buổi luyện tập họ cùng nhau thảo luận về bài tập ở cùng một phòng học nào đó. Họ muốn phòng học này phải có khoảng cách bằng nhau khi đi đến hai phòng học của Tâm và Gia Huy để cả hai bạn không một ai phải đi quá xa.

Khoảng cách giữa hai phòng học là số hành lanh họ phải đi qua trên con đường.

Vì đang trong giai đoạn gấp rút chuẩn bị, họ sẽ liên tục luyện tập trong ~m~ ngày và mỗi ngày hai bạn có thể chuyển địa điểm luyện tập. Bạn hãy giúp Tâm và Gia Huy tìm số phòng học thỏa mãn với mong muốn của họ.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ - số phòng học tại trường đại học của Tâm và Gia Huy.
• ~n-1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~u, v~ cho biết có hành lang nối giữa phòng học ~u~ và phòng học ~v~.
• Dòng tiếp theo gồm số nguyên dương ~m~ - số ngày luyện tập.
• ~m~ dòng cuối cùng, dòng thứ ~i~ dòng gồm hai số nguyên dương ~a_i, b_i~ cho biết vào ngày thứ ~i~, Tâm sẽ luyện tập ở phòng ~a_i~ còn Gia Huy ở phòng ~b_i~.

Constraint

• ~1 \le n, m \le 10^5~
• ~1 \le u, v \le 10^5~
• ~1 \le a_i, b_i \le 10^5~

Subtask

• Subtask ~1~ ~(30\%)~: ~n, m \le 2000~.
• Subtaks ~2~ ~(70\%)~: Không có điều kiện gì thêm.

Output

• Gồm ~m~ dòng, dòng thứ ~i~ in ra số phòng có khoảng cách đến phòng học của Tâm và Gia Huy là như nhau.

Sample Input 1:

4
1 2
1 3
2 4
1
2 3

Sample Output 1:

1

Explanation 1:

Chỉ có phòng ~1~ thỏa mãn khoảng cách đến phòng ~2, 3~ bằng nhau (bằng ~1~).

Sample Input 2:

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

Sample Output 2:

0
2

Cho cây ~n~ đỉnh. Mỗi đỉnh được tô bằng một màu nào đó.

Gốc của cây là ~1~, đỉnh ~u~ có màu ~c_u~.

Cho ~q~ truy vấn, mỗi truy vấn có dạng như sau:

• ~u,k~: tìm số màu ~x~ sao cho trong ~subtree~ của ~u~ thì màu ~x~ xuất hiện ít nhất ~k~ lần.

Input

• Dòng đầu tiên gồm ~2~ số nguyên ~n~ và ~q~.
• Dòng thứ ~2~ gồm ~n~ số nguyên ~c_1,c_2,...,c_n~ miêu tả màu của cây.
• ~n-1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~u~ và ~v~, miêu tả cạnh nối giữa ~u~ và ~v~.
• ~q~ dòng sau, mỗi dòng gồm ~2~ số nguyên ~u,k~ miêu tả truy vấn.

Subtask

• Subtask ~1~ ~(20\%)~ : ~n,q \le 1000~
• Subtask ~2~ ~(40\%)~ : ~c_i \le 100~
• Subtask ~3~ ~(40\%)~ : Không giới hạn gì thêm

Constraints

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

Output

• In ra đáp án cho mỗi truy vấn loại.

Sample Input 1

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

Sample Output 1

2
2
1
0
1

Cho một cây vô hướng gồm ~n~ đỉnh. Đỉnh thứ ~i~ ~(1 \le i \le n)~ có trọng số là ~a_i~, cạnh thứ ~i~ ~(1 \le i \le n-1)~ có trọng số là ~w_i~.

Định nghĩa hàm ~dist(u,v)~ là tổng trọng số của các cạnh trên đường đi đơn từ đỉnh ~u~ tới đỉnh ~v~.

Hãy tìm ~max(dist(u,v) \times gcd(a_u,a_v)) \forall u,v \in [1,n]~.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~.
• Dòng thứ hai gồm ~n~ số nguyên, số thứ ~i~ là ~a_i~ miêu tả trọng số của đỉnh thứ ~i~.
• ~n-1~ dòng tiếp theo, dòng thứ ~i~ gồm ba số nguyên dương ~u_i,v_i,w_i~ miêu tả cạnh thứ ~i~ của cây.

Constraint

• ~1 \le n \le 10^5~
• ~1 \le a_i \le 10^5~
• ~1 \le w_i \le 10^5~

Subtask

• Subtask ~1~ ~(30\%)~: ~n \le 2000~.
• Subtask ~2~ ~(20\%)~: ~a_i = 1; \forall i \in [1,n]~
• Subtask ~3~ ~(30\%)~: ~n,a_i \le 4 \times 10^4~
• Subtask ~4~ ~(20\%)~: Không có ràng buộc gì thêm.

Output

• In ra kết quả của bài toán.

Sample Input 1:

2
10 10
1 2 10

Sample Output 1:

100

Cho một cây ~n~ nút và ta định nghĩa nút ~1~ là gốc của cây.

Bây giờ ta có ~q~ truy vấn, mỗi truy vấn có dạng: ~l_i,r_i~ ~(1 \le l_i \le r_i \le n)~.

Yêu cầu: Ứng với mỗi truy vấn, ta in ra LCA của tất cả các nút từ ~l_i~ đến ~r_i~.

Input

• Dòng đầu vào đầu tiên chứa số nguyên ~n~ - thể hiện số nút của cây.

• ~n-1~ dòng tiếp theo: mỗi dòng gồm ~2~ số nguyên ~x,y~ - thể hiện cạnh nối giữa hai đỉnh ~x~ và ~y~.

• Dòng tiếp theo, chứa số ~q~ thể hiện số lượng truy vấn.

• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l_i,r_i~ ~(1 \le l_i \le r_i\le n)~.

Constraints

• ~1 \le n \le 3*10^5~.

Subtask

• Subtask ~1~ ~(50\%)~: ~n \le 2000~.
• Subtask ~2~ ~(50\%)~: Không có điều kiện gì thêm.

Output

• Ứng với mỗi truy vấn, in ra đáp án cần tìm.

Sample Input 1:

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

Sample Output 1:

4
1

Cho một cây ~n~ đỉnh với các cạnh có trọng số là các số tự nhiên. Cần trả lời ~Q~ truy vấn dạng ~u, v, k~: Xét các cạnh nằm trên đường đi đơn từ ~u~ đến ~v~ mà có trọng số không vượt quá ~k~, tính xor các trọng số của các cạnh này. Ở đây xor là phép toán "~∧~" (hay nim, hay hoặc triệt tiêu).

Input

• Dòng đầu chứa hai số nguyên dương: ~n~ ~Q~ ~(1 \le n,Q \le 10^5)~;
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa ba số tự nhiên mô tả một cạnh: ~x, y, w~ ~(w \le 2^{31})~;
• ~Q~ dòng tiếp theo, mỗi dòng chứa ba số tự nhiên mô tả một truy vấn: ~u, v, k~ ~(k \le 2^{31})~.

Output

• Với mỗi truy vấn, in ra kết quả trên một dòng

Example

Sample Input

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

Sample Output

0
4
0
4

Chúng ta đều biết thuyết tiến hóa của Darwnin là một học thuyết có tính khoa học, hệ thống, có nhiều bằng chứng thực nghiệm. Ấy vậy mà gần đây có không ít người, có thể là bao gồm những học sinh không thích môn sinh học, tỏ ra không tin tưởng và thậm chí phản bác nó một cách vô căn cứ.

Cả hai phe, ủng hộ và không ủng hộ, mỗi bên đều đưa ra một mô hình cây tiến hóa, trong đó các loài được đánh số từ ~1~ đến ~n~. Nếu ~x~ là tổ tiên của ~y~ thì ở trên cây, ~x~ sẽ nằm trên đường đi đơn từ ~y~ đến ~1~. Hai cây này cũng có những điểm giống nhau, chẳng hạn cả hai đều công nhận ~1~ là tổ tiên của tất cả các loài. Để đánh giá mức độ giống nhau của hai mô hình, với mỗi ~y~, cần tính số lượng ~x~ là tổ tiên của ~y~ ở cả hai mô hình đó.

Input

• Dòng đầu chứa số nguyên dương: ~n~; ~(1 ≤ n ≤ 5 × 10^5)~
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số tự nhiên mô tả một cạnh của cây thứ nhất: ~x, y~;
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số tự nhiên mô tả một cạnh của cây thứ hai: ~x, y~;

Output

• Ghi ra ~n~ số, số thứ ~y~ là số lượng ~x~ là tổ tiên của ~y~ ở cả hai mô hình

Example

Sample Input

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

Sample Output

1 2 2 2 3

Đất nước "vui vẻ" có ~n~ thành phố được đánh số từ ~1~ đến ~n~, và ~n - 1~ con đường hai chiều nối một số cắp thành phố. Giữa hai thành phố bất kỳ luôn có đường đi trực tiếp hoặc đường đi gián tiếp qua một số thành phố trung gian.

Có ~k~ thành phố nổi tiếng mà khách du lịch luôn muốn đến thăm. Khách du lịch sẽ bắt đầu từ một thành phố nào đó trong ~n~ thành phố, đi theo các con đường nối giữa các thành phố để thăm đủ ~k~ thành phố nổi tiếng (mỗi con đường/thành phố có thể đi qua nhiều lần). Đất nước khá là vui vẻ trừ giá taxi ở đây, nên khách du lịch muốn chọn lộ trình có tổng độ dài phải đi là nhỏ nhất. Nhưng bạn biết đấy, sẽ thật phiền phức khi vừa đi du lịch vừa phải code, họ sẽ rất vui vẻ nếu nhận được sự giúp đỡ của bạn.

Input

• Dòng đầu chứa hai số nguyên dương ~n, k~ ~(1 \le k \le n \le 10^5)~
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa ~3~ số nguyên dương ~u, v, L~; cho biết có một con đường độ dài ~L~ nối giữa hai thành phố ~u, v~ ~(1 \le u,v \le v, L \le 10^9)~
• Dòng tiếp theo chứa ~k~ số nguyên dương là số hiệu của ~k~ thành phố nổi tiếng.

Subtask:

• Subtask ~1~ (~30\%~ số điểm): ~n \le 2000~.
• Subtask ~2~ (~40\%~ số điểm): ~k = n~.
• Subtask ~3~ (~30\%~ số điểm): Không có giới hạn gì thêm.

Output

• Gồm ~n~ dòng, dòng thứ ~i~ là tổng độ dài phải đi của lộ trình tốt nhất nếu khách du lịch bắt đầu từ thành phố ~i~.

Example

Sample Input

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

Sample Output

13
12
11
10
13
13
12
12
11
13
13
11
10