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~.

Scoring

Example

Sample Input

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

Sample Output

1
3
-1

Một đế chế đang xây dựng mạng lưới cho các hành tinh trong nó. Đế chế gồm có ~N~ hành tinh được biểu diễn như các điểm trong không gian 3 chiều. Chi phí phải chi cho việc nối giữa hành tinh ~A~ và hành tinh ~B~ là ~min~{ |~x_A - x_B~|, |~y_A - y_B~|, |~z_A~ - ~z_B~| } với (~x_A~, ~y_A~, ~z_A~), (~x_B~, ~y_B~, ~z_B~) là tọa độ của hành tinh ~A~, ~B~ trong không gian 3 chiều.

Đế chế dự tính sẽ xây dựng ~N – 1~ cầu nối như vậy để các hành tinh liên thông với nhau và chi phí để trả sao cho phải nhỏ nhất có thể.

Input

• Dòng đầu là số hành tinh ~N~.
• N dòng sau mỗi dòng là tọa độ của một hành tinh.

Output

• Ghi trên một dòng duy nhất chi phí nhỏ nhất có thể.

Example

Sample Input 1

5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19

Sample Output 1

4

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.

Example

Sample Input

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

Sample Output

9
8
11
8
8
8
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~.

Scoring

Example

Sample Input 1

3 3
1 2 1
2 3 1
3 1 1

Sample Output 1

3

Sample Input 2

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

Sample Output 2

2

Sample 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

Sample 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.

Scoring

Example

Sample 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

Sample Output 1

Yes Yes No Yes No No No 

Cho một đơn đồ thị liên thông, vô hướng, có trọng số gồm:

• ~N~ đỉnh - được đánh số từ ~1~ đến ~N~;
• ~M~ cạnh - cạnh ~(u, v, c)~ mô tả đường đi hai chiều trực tiếp giữa hai đỉnh ~u~ và đỉnh ~v~, có chi phí là ~c~;
• ~K~ đỉnh đặc biệt, phân biệt có tính chất như sau: trên đường đi, khi ở một đỉnh đặc biệt có thể di chuyển đến một đỉnh đặc biết bất kỳ trước đó đã đi qua mà không mất chi phí.

Tìm đường đi có tổng chi phí nhỏ nhất đi qua toàn bộ các đỉnh đặc biệt (đường đi có thể xuất phát từ một đỉnh bất kì).

Input

• Dòng đầu tiên gồm ba số nguyên dương ~N, M~ và ~K \ (2\le K\le N; \ N, M\le 10^5)~ mô tả số lượng đỉnh, số lượng cạnh và số lượng đỉnh đặc biệt;
• Dòng thứ hai gồm ~K~ số nguyên dương ~S \ (S \le N)~ mô tả các đỉnh đặc biệt;
• ~M~ dòng sau, mỗi dòng gồm ba số nguyên dương ~u, v, c \ (u, v\le N; \ c\le 10^9)~ mô tả các cạnh của đồ thị.

Output

Một số nguyên duy nhất là tổng chi phí nhỏ nhất của đường đi thoả mãn yêu cầu.

Scoring

Example

Sample Input 1

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

Sample Output 1

5

Giải thích

Có thể đi theo đường đi: ~4 \rightarrow 1 \rightarrow 2 \rightarrow 3~

Sample Input 2

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

Sample Output 2

7

Giải thích

Có thể đi theo đường đi: ~1 \rightarrow 2 \rightarrow 3 \rightarrow 1\rightarrow 2\rightarrow 5~

Thành phố nơi Nam sinh sống đã xay dựng hệ thống Wi-Fi công cộng để phục vụ khách du lịch và người dân trong thành phố. Hệ thống bao gồm ~n~ trạm phát sóng được đánh số từ ~1~ đến ~n~, trạm thứ ~i~ được đặt ở vị trí tương ứng với tọa độ ~(x_i, y_i)~ trên bản đồ mặt phẳng tọa độ của thành phố. Các trạm phát sóng này đều có mức độ phủ sóng là ~s~. Hai trạm phát sóng ~i~ và ~j~ có thể truyền thông tin cho nhau bằng sóng nếu ~\left|x_i - x_j \right| + \left| y_i - y_j \right| \le s~, hoặc trạm phát sóng ~i~ có thể truyền thông tin qua một số trạm phát sóng trung gian để tới được trạm phát sóng ~j~. Một nhóm các trạm phát sóng gọi là liên thông nếu như hai trạm bất kỳ trong nhóm có thể truyền thông tin cho nhau. Mỗi nhóm liên thông chỉ cần một đường truyền cung cấp internet để tất cả các trạm phát sóng này đều có thể phát được mạng internet cho người dân sử dụng.

Tuy nhiên, sau một thời gian sử dụng, chi phí duy trì hoạt động của hệ thống này là rất lớn, trong đó chi phí sử dụng mạng internet hàng tháng là chiếm nhiều nhất. Chi phí sử dụng mạng internet tỉ lệ thuận với số đường truyền cung cấp internet. Do đó, chính quyền thành phố muốn giảm thiểu số lượng truyền cung cấp internet mà vẫn bảo đảm tất cả các trạm đều có mạng internet bằng cách thiết kế các đường dây cáp kết nối trực tiếp một số trạm phát sóng với nhau. Với hai trạm phát sóng ~u~ và ~v~ chưa truyền được thông tin cho nhau, khi kết nối trực tiếp chúng bằng đường dây cáp, hai trạm phát sóng này có thể truyền tin cho nhau, vì vậy, nếu một trong hai trạm có mạng internet thì trạm còn lại cũng có mạng internet và toàn bộ nhóm liên thông chứa trạm này đều phát được mạng internet, do đó, có thể giảm độ một đường truyền cung cấp internet. Chi phí để kết nối hai trạm phát sóng ~u~ và ~v~ bằng đường dây cáp là ~\left | x_u - x_v \right| + \left| y_u - y_v \right|~. Chính quyền thành phố muốn xây dựng phương án giảm đi ~k~ đường truyền cung cấp internet mà vẫn bảo đảm trạm phát sóng nào cũng có mạng internet bằng cách sử dụng thêm ~k~ đường dây cáp kết nối trực tiếp sao cho tổng chi phí kết nối bằng dây cáp là nhỏ nhất.

Yêu cầu: Cho biết số lượng và vị trí của ~n~ trạm phát sóng, mức độ phủ sóng ~s~ của các trạm phát sóng và số lượng ~k~ đường truyền cung cấp internet cần giảm đi, hãy tính chi phí nhỏ nhất để kết nối các trạm phát sóng bằng dây cáp sao cho trạm phát sóng nào cũng có mạng internet.

Dữ liệu

Vào từ file văn bản INTERNET.INP:

• Dòng đầu tiên chứa ba số nguyên dương ~n, s, k~ (~n \le 10^5~; ~s \le 10^9~; ~k \le 20~);
• Dòng thứ ~i~ trong số ~n~ dòng tiếp theo chứa hai số nguyên không âm ~x_i, y_i~ mô tả vị trí trạm phát sóng thứ ~i~ (~1 \le i \le n~; ~x_i, y_y \le 10^9~). Dữ liệu bảo đảm không có hai trạm phát sóng nào có tọa độ trùng nhau và số lượng đường truyền cung cấp internet cần sử dụng cho hệ thống ban đầu lớn hơn ~k~.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Kết quả

Ghi ra file văn bản INTERNET.OUT một số nguyên duy nhất là chi phí nhỏ nhất để kết nối các trạm phát sóng thỏa mãn yêu cầu.

• Có ~20\%~ số test ứng với ~20\%~ số điểm của bài thỏa mãn: ~n \le 1000~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thỏa mãn tọa độ tất cả các trạm phát sóng đều nằm trên một đường thẳng;
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thỏa mãn giá trị tọa độ mỗi trạm phát sóng không vượt quá ~1000~;
• ~40\%~ số test còn lại ứng với ~40\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

5 4 1
1 1
3 4
8 5
5 5
7 1

Output

5

Giải thích

Ban đầu có ~3~ nhóm liên thông là {Trạm 1}, {Trạm 2, Trạm 3, Trạm 4} và {Trạm 5}. Phương án cho chi phí nhỏ nhất để giảm bớt một đường truyền cung cấp internet là nối cặp giữa Trạm 3 và Trạm 5 cho chi phí bằng ~|8 - 7| + |5 - 1| = 5~.