Đất nước ~ABC~ gồm ~n~ thành phố nối với nhau bởi ~m~ con đường. Con đường thứ ~i~ nối hai chiều giữa hai thành phố ~u_i~ và ~v_i~, với độ dài là ~1~.

Luật pháp của ~ABC~ rất lạ, có ~k~ bộ ba được coi là "xấu" ~(a_i,b_i,c_i)~, khi di chuyển, bạn không được đi liên tiếp qua các thành phố ~a_i,b_i,c_i~. Lưu ý rằng, vẫn có thể đi theo thứ tự liên tiếp ~a_i,c_i,b_i~.

Bạn cần đi từ thành phố ~1~ tới ~n~, hãy tìm cách di chuyển ngắn nhất.

Input

• Dòng đầu chứa ba số nguyên ~n,m,k~ ~(n \le 3000; 1 \le m \le 2 \times 10^4; 0 \le k \le 10^5)~.
• ~m~ dòng tiếp theo, mỗi dòng gồm ba số nguyên dương ~u_i, v_i~ ~(1 ≤ u_i, v_i ≤ n; u_i ≠ v_i)~.
• ~k~ dòng sau, mỗi dòng gồm ba số nguyên dương ~a_i,b_i,c_i~ ~(1 ≤ a_i, b_i, c_i ≤ n) ~

Output

• Dòng đầu chứa một số ~d~ là đường đi ngắn nhất, nếu không có hãy in ra ~-1~.

Subtask

• Subtask ~2~: Không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

2

Đất nước U có ~n~ thành phố, đánh số từ 1 đến ~n~. Các thành phố được nối với nhau bởi hệ thống giao thông gồm m tuyến đường hai chiều, mỗi tuyến đường nối trực tiếp một cặp thành phố, đảm bảo luôn có đường đi lại giữa hai thành phố bất kì trong nước (trực tiếp hoặc đi qua một số thành phố khác). Giữa hai thành phố bất kì không có quá một tuyến đường nối trực tiếp.

Có tổng cộng ~b~ kho lương thực được đặt trên khắp cả nước, mỗi kho nằm ở một thành phố khác nhau. Để bảo vệ đất nước khỏi quân xâm lược, Thủ tướng U đã chọn ra ~r~ thành phố khác nhau để đặt trại quân sự.

Yêu cầu: Để giải quyết vấn đề lương thực cho quân doanh, với mỗi thành phố được đặt trại quân sự, nhiệm vụ của bạn là tính toán số tuyến đường ít nhất cần đi nếu xuất phát từ thành phố đó đến một kho lương thực bất kì.

Input

• Dòng thứ nhất gồm bốn số nguyên: ~n,m,b,r\ (2 \le n \le 5.10^5; 1 \le m \le 5.10^5; 1 \le b,r \le n)~
• Dòng thứ hai gồm ~b~ số nguyên là chỉ số của các thành phố được đặt kho lương thực;
• Dòng thứ ba gồm ~r~ số nguyên là chỉ số của các thành phố được đặt trại quân sự;
• ~m~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~u~ và ~v~ thể hiện có một tuyến đường hai chiều nối trực tiếp hai thành phố ~u~ và ~v~.

Output

• Xuất ra ~r~ số nguyên trên cùng một dòng là kết quả tính được của các thành phố được đặt trại quân sự theo thứ tự của dữ liệu.

Subtask

• Subtask 1: (40% số test): ~n \le 5000~
• Subtask 2: (60% số test): Không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

1 2 1

Explanation 1

• Thành phố ~1~: ~1 → 2~
• Thành phố ~4~: ~4 → 3~
• Thành phố ~5~: ~5 → 4 → 3~

Cho một đơn đồ thị vô hướng gồm ~n~ đỉnh và ~m~ cạnh. Độ dài của mỗi cạnh là ~1~. Ta định nghĩa khoảng cách giữa hai đỉnh ~u~ và ~v~ là độ đường đi ngắn nhất từ ~u~ đến ~v~.

Ban đầu, tất cả các đỉnh được tô màu ~0~. Cho ~q~ truy vấn, truy vấn thứ ~i~ yêu cầu tô màu ~c_i~ cho tất cả các đỉnh có khoảng cách đến ~u_i~ nhỏ hơn hoặc bằng ~d _i~.

Hãy cho biết màu của từng đỉnh sau khi thực hiện xong ~q~ truy vấn trên.

Input

• Dòng đầu ghi hai số nguyên dương ~n,m~ miêu tả số cạnh và số đỉnh.
• ~m~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~u_i~ và ~v_i~ ~(u_i, v_i \le n)~ mô tả một cạnh trong đồ thị. Dữ liệu vào đảm bảo đồ thị đã cho là đơn đồ thị.
• Dòng tiếp theo ghi số nguyên dương ~q~ - miêu tả số truy vấn.
• ~q~ dòng tiếp theo, mỗi dòng ghi ba số nguyên ~u_i, d_i, c_i~

Giới hạn

• ~n,m,q \le 10^5~.
• ~d_i \le 10~.
• ~c_i \le 10^5~.

Output

In ra ~n~ dòng, dòng thứ ~i~ in ra một số nguyên duy nhất - màu của đỉnh ~i~ sau khi thực hiện ~q~ truy vấn trên.

Sample Input

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

Sample Output

0
1
1
2
3
2
1

Một công ty có ~n~ nhân viên đang trong quá trình tái cơ cấu tổ chức. Sau quá trình này, sơ đồ cấp bậc trong công ty tạo thành một đồ thị dạng cây gồm ~n~ đỉnh, mỗi đỉnh là sếp của tất cả các con của chúng.

Mỗi nhân viên có một danh sách gồm ~k_i~ người họ đồng ý làm sếp trực tiếp của mình. Ngoài ra, mỗi nhân viên cần được tính toán lại lương sao cho lương của mỗi người sếp phải lớn hơn tổng lương của những nhân viên người đó quản lí.

Hãy tìm cách tái cơ cấu lại công ty sao cho tổng lương phải trả cho ~n~ nhân viên là nhỏ nhất có thể.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ - số nhân viên trong công ty.
• ~n~ dòng tiếp theo, mỗi dòng bắt đầu bởi số nguyên ~k_i~. Sau đó là ~k_i~ số nguyên dương là danh sách những người được nhân viên thứ ~i~ đồng ý làm sếp của mình.

Output

• Gồm một số nguyên dương là tổng lương phải trả nhỏ nhất.

Subtask

• Subtask 1 ~(20\%)~: ~2 \le n \le 10, \sum{k_i} \le 20~
• Subtask 2 ~(45\%)~: ~2 \le n \le 200, \sum{k_i} \le 200~.
• Subtask 3 ~(35\%)~: ~2 \le n \le 5000, \sum{k_i} \le 10000~.

Sample Input 1

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

Sample Output 1

8

Explanation 1

    3
   / \ 
  4   2
 /
1

Lương của từng người là ~[1, 1, 2, 4]~.

Alice vừa mới lạc vào một vùng đất rất kì lạ tên là "Bruhderland". Đây là một vùng đất lai giữa "Wonderland" và "Borderland", nơi có phép màu và cả những trò chơi sinh tử.

Bruhderland được biểu diễn bằng một ma trận ~n \times m~, với ô ~(i,j)~ là một trong các kí tự sau:

• .: có nghĩa là ô đất trống, có thể đi vào.
• *: có nghĩa là ô có một tảng đá, không thể đi vào.
• A: có nghĩa là có một trò chơi với độ khó ~A~ ở ô này, Alice rất giỏi nên sẽ có thể vượt qua trò chơi, nhưng sẽ mất ~1~ sức lực.
• B: có nghĩa là có một trò chơi với độ khó ~B~ ở ô này, Alice vẫn sẽ có thể vượt qua trò chơi, nhưng sẽ mất ~2~ sức lực.

Giả sử, Alice đang ở ô ~(i,j)~, cô có thể đi sang ~4~ ô kề cạnh nếu như ô đó không vượt qua ngoài bảng và không chứa tảng đá nào. Như đã nói, Bruhderland có cả yếu tố phép màu, vậy nên khi vào đây, cô đã học được cách đọc thần chú để phá hủy một tảng đá bất kì mà không mất sức lực nào (nghĩa là có thể đi vào ô chứa tảng đá vừa bị phá hủy), tuy nhiên do năng lực giới hạn, Alice chỉ có thể đọc thần chú ~k~ lần mà thôi.

Alice đang ở ô ~(1,1)~, để thoát ra khỏi Bruhderland, cô sẽ cần đến ô ~(n,m)~. Tuy nhiên, do khá lười tham gia vào các trò chơi, Alice muốn thoát ra khỏi Bruhderland sao cho tốn ít sức lực nhất.

Quan trọng: Dữ liệu đảm bảo kết quả không quá ~2500~.

Input: BRUHDERLAND.INP

• Dòng đầu tiên ghi ~3~ số nguyên dương ~n,m,k~ ~(1 \le n,m \le 1000, 0 \le k \le 5)~.
• ~n~ dòng sau, dòng thứ ~i~ gồm một xâu kí tự độ dài ~m~ miêu tả hàng thứ ~i~ của ma trận.
• Dữ liệu đảm bảo ô ~(1,1)~ là kí tự . và luôn tồn tại cách đi từ ~(1,1)~ tới ~(n,m)~ nếu sử dụng thần chú một cách hợp lý.

Output: BRUHDERLAND.OUT

• In ra một số nguyên dương là số sức lực ít nhất cần tiêu tốn để đến được ô ~(n,m)~.

Scoring:

• Subtask ~1~ ~(10\%)~: ~ n\times m \le 10^5~, ~k = 0~ và các ô khác ô ~(1,1)~ chỉ gồm kí tự A
• Subtask ~2~ ~(15\%)~: ~ n\times m \le 10^5~, ~k = 0~ và các ô khác ô ~(1,1)~ không có kí tự B và ..
• Subtask ~3~ ~(10\%)~: ~k = 0~ và các ô khác ô ~(1,1)~ không có kí tự B.
• Subtask ~4~ ~(10\%)~: Các ô khác ô ~(1,1)~ không có kí tự B.
• Subtask ~5~ ~(15\%)~: ~n \times m \le 10^5~ và ~k = 0~.
• Subtask ~6~ ~(20\%)~: ~n \times m \le 10^5~.
• Subtask ~7~ ~(20\%)~: Không có giới hạn gì thêm.

Sample Input 1

4 4 0
.AAA
AAAA
AAAA
AAAA

Sample Output 1

6

Sample Input 2

5 4 0
.AAA
***A
AAAA
A***
AAAA

Sample Output 2

13

Sample Input 3

5 4 0
.AAA
***B
AAAA
A**B
BAAA

Sample Output 3

9

Sample Input 4

5 4 2
.BAA
****
AABA
A***
BABA

Sample Output 4

6

Cho số nguyên dương ~n~ và dãy số nguyên không âm ~a_1,a_2,...,a_n~. Ta định nghĩa khoảng cách giữa hai số ~x~ và ~y~ là số lần ít nhất phải thực hiện các thao tác sau để biến ~x~ thành ~y~:

• Chọn một lũy thừa của ~2~, kí hiệu là ~2^z~.

• Thực hiện phép gán ~x = x~ ~\oplus~ ~2^z~

Trong đó ~\oplus~ là phép toán ~XOR~ được cho bởi bảng giới đây:

Việc thực hiện phép ~XOR~ trên hai số nguyên là thực hiện phép ~XOR~ trên từng bit trong biểu diễn nhị phân của hai số.

Yêu cầu: Với mỗi số ~a_1,a_2,...,a_n~; hãy tìm một số khác trong dãy có khoảng cách tới số đó là bé nhất.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ (~2\le n \le 5 \times 10^5~) là số phần tử của dãy.

• Dòng thứ hai chứa ~n~ số nguyên không âm ~a_1,a_2,...,a_n~ (~a_i \le 5 \times 10^5~) mô tả dãy được cho.

Output

• ~n~ số nguyên, mỗi số nguyên là khoảng cách gần nhất ứng với một phần tử trong phương án tối ưu tìm được.

Scoring

Sample Input 1

6
1 2 4 3 8 15

Sample Output 1

1 1 2 1 2 2

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

Ở một vương quốc nọ có ~n~ thành phố, được đánh số từ ~1~ đến ~n~. Mạng lưới giao thông của vương quốc gồm ~m~ con đường, con đường thứ ~i~ nối hai thành phố ~u_i~ và ~v_i~ với độ dài đúng bằng ~1~ ki-lô-mét.

Có ~k~ dự án nhà máy điện đang được triển khai, dự án thứ ~j~ sẽ xây một nhà máy điện đặt tại thành phố ~p_j~, cung cấp điện cho tất cả các thành phố nằm trong bán kính ~r_j~ ki-lô-mét (giả sử rằng quãng đường di chuyển trong nội thành là bằng ~0~). Nhà vua đang băn khoăn, những thành phố nào đã được cấp điện, và những thành phố nào chưa được cấp điện? Hãy giúp nhà vua giải quyết bài toán này nhé.

Input

Dòng đầu chứa ba số nguyên ~n~, ~m~, ~k~ (~2 \le n, m \le 2 \times 10^5~; ~0 \le k \le 5 \times 10^5~).

~m~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~u_i~, ~v_i~ (~1 \le u_i, v_i \le n~; ~u_i \ne v_i~) mô tả con đường thứ ~i~.

~k~ dòng tiếp theo, dòng thứ ~j~ chứa hai số nguyên ~p_j~, ~r_j~ (~1 \le p_j \le n~; ~0 \le r_j \le 10^9~) mô tả dự án thứ ~j~.

Output

Gồm một dòng duy nhất chứa một xâu nhị phân gồm ~n~ kí tự, kí tự thứ ~i~ bằng "1" nếu thành phố thứ ~i~ đã được cấp điện, ngược lại kí tự thứ ~i~ bằng "0" nếu thành phố thứ ~i~ chưa được cấp điện.

Scoring

• Subtask ~1~ (~40\%~ số điểm): ~n, m \le 1000~.
• Subtask ~2~ (~30\%~ số điểm): ~r_1 = r_2 = \dots = r_{k - 1} = r_k~.
• Subtask ~3~ (~30\%~ số điểm): Không có ràng buộc gì thêm.

Example

Input 1

4 3 1
1 2
1 3
2 4
2 1

Output 1

1101

Input 2

6 8 2
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
6 0
3 1

Output 2

101111

Software and cathedrals are much the same – first we build them, then we pray 😈

Dưới lòng đất của HNA là hệ thống đường ngầm dày đặc gồm ~n~ địa điểm đánh số từ ~1~ đến ~n~. Có ~m~ đoạn đường ngầm, đoạn đường ngầm thứ ~i~ kết nối địa điểm ~u_i~ và ~v_i~ có chi phí là ~c_i~, nghĩa là muốn kích hoạt sử dụng đoạn đường hầm này phải trả chi phí là ~c_i~. LetterC67 và ~aúR là đôi bạn thân đang hoạt động dưới lòng đất này.

Buổi sáng, LetterC67 cần đi từ ~A~ đến ~B~, và tất nhiên cậu chọn tuyến đường sao cho cần trả ít chi phí nhất.

Buổi chiều, ~aúR cần đi từ ~C~ đến ~D~, nhưng may thay, những đoạn đường hầm mà buổi sáng LetterC67 đã trả chi phí để kích hoạt rồi thì ~aúR có thể sử dụng mà không cần trả chi phí nữa.

Hãy hãy tính xem ~aúR cần trả chi phí ít nhất là bao nhiêu?

Input: tunnel.inp

• Dòng đầu tiên gồm hai số nguyên ~n, m~.
• Dòng thứ hai là bốn số nguyên ~A, B, C, D~.
• ~m~ dòng tiếp theo, mỗi dòng gồm ba số nguyên ~u_i, v_i, c_i~.
• Dữ liệu đảm bảo từ một địa điểm có thể đi đến mọi địa điểm khác, không có hai đoạn đường hầm nối cùng một cặp địa điểm.

Output: tunnel.out

• In ra một số nguyên là kết quả của bài toán.

Note

• Trong mọi test: ~A \neq B, C \neq D~, ~1 \le u_i < v_i \le n~, ~1 \le c_i \le 10^9~.
• Subtask 1 (~15\%~ số điểm): ~A=C~;
• Subtask 2 (~15\%~ số điểm): Có duy nhất một tuyến đường từ ~A~ đến ~B~ có giá trị nhỏ nhất;
• Subtask 3 (~30\%~ số điểm): ~n \le 300~;
• Subtask 4 (~40\%~ số điểm): ~2 \le n \le 10^5, 1 \le m \le 2 \times 10^5~

Ví dụ

Input:

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

Output:

2

Giải thích:

• Chỉ có duy nhất một đường đi ngắn nhất từ ~1~ đến ~6~ là ~1-2-3-5-6~, nên LetterC67 sẽ sử dụng tuyến đường này.
• ~aúR sẽ chỉ phải trả chi phí thêm đoạn đường hầm ~4-5~ với giá trị ~2~ đến di chuyển từ ~1~ đến ~4~.

Châu đang muốn quảng bá dòng xe điện Cessla của mình bằng cách giới thiệu mạng lưới các trạm sạc của Cessla. Anh ấy đã xác định được ~N (2 \le N \le 5*10^4)~ điểm quan tâm được đánh số từ ~1~ đến ~N~, trong đó ~C(1 \le C \le N)~ trạm đầu tiên là các trạm sạc và còn lại là các điểm du lịch. Các điểm này được kết nối với nhau bởi ~M(1\le M \le 10^5)~ đường hai chiều, đường thứ ~i~ nối hai điểm phân biệt ~u_i~ và ~v_i~ và có độ dài ~l_i~ dặm ~(1\le l_i \le 10^9)~.

Cessla có thể di chuyển với quãng đường lên tới ~2R~ dặm ~(1 \le R \le 10^9)~ trong một lần sạc, cho phép nó đến bất kỳ điểm đến nào trong phạm vi ~R~ dặm tính từ trạm sạc. Một điểm đến được coi là kết nối tốt nếu có thể đến được điểm đến đó từ ít nhất ~K(1\le K\le 10)~ trạm sạc riêng biệt. Nhiệm vụ của bạn là hỗ trợ John xác định các điểm đến du lịch có kết nối tốt.

Input

Dòng đầu tiên chứa năm số nguyên ~N,M,C,R,K~. Mỗi dòng trong ~M~ dòng tiếp chứa ba số nguyên cách nhau bằng dấu cách ~u_i,v_i,l_i~ sao cho ~u_i \ne v_i~. Các trạm sạc được đánh số ~1,2,...,C~. Các điểm còn lại đều là các điểm du lịch.

Output

Đầu tiên, in ra số lượng điểm đến du lịch có kết nối tốt trên một dòng. Sau đó, liệt kê tất cả các điểm đến du lịch có kết nối tốt theo thứ tự tăng dần, mỗi điểm trên một dòng riêng biệt.

Scoring

• Subtask ~1~: ~K=2~, ~N \le 500~ và ~M \le 1000~.
• Subtast ~2~: ~K=2~.
• Subtask ~3~: Không có điều kiện gì thêm.

Example

Sample Input 1

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

Sample Output 1

1
2

Explanation

Chúng ta có một trạm sạc ở ~1~. Từ trạm sạc này, chúng ta có thể đến điểm ~2~ (vì nó cách ~1~ khoảng cách là ~3~), nhưng không thể đến điểm ~3~ (vì nó cách ~1~ khoảng cách là ~5~). Như vậy chỉ có điểm ~2~ là kết nối tốt.

Sample Input 1

4 3 2 101 2
1 2 1
2 3 100
1 4 10

Sample Output 1

2
3
4

Explanation

Chúng ta có các trạm sạc tại ~1~ và ~2~, và cả hai điểm ~3~ và ~4~ đều cách hai điểm ~1~ và ~2~ khoảng cách là ~101~. Vì vậy, cả hai điểm ~3~ và ~4~ đều có kết nối tốt.

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ộ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~ ~(1 \le n \le 10^5)~.
• 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ể.

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.

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