Bài tập

Thời gian vừa qua, mưa bão, lũ quét và sạt lở đã làm hư hỏng, đứt rất nhiều tuyến cáp quang nối giữa các trạm thu phát sóng trong thành phố.

Theo khảo sát, có \(n\) trạm (được đánh số từ \(1\) đến \(n\)) và \(m\) tuyến cáp (được đánh số từ \(1\) đến \(m\)) hư hỏng nặng cần phải sửa chữa gấp. Chi phí để sửa chữa tuyến cáp thứ \(i\) nối giữa trạm \(u_i\) và trạm \(v_i\) là \(w_i\).

Chính quyền thành phố hiện có hai phương án ưu tiên sửa chữa độc lập, cả hai đều nhắm đến mục tiêu tối ưu hóa tổng chi phí:

• Dự án loại \(1\): Sửa chữa một số tuyến cáp sao cho \(k\) trạm trọng điểm \(i_1,i_2,\ldots,i_k\) liên lạc được với nhau (tức là có liên lạc giữa bất kỳ hai trạm \(i_u\) và \(i_v\) nào thuộc nhóm này).
• Dự án loại \(2\): Sửa chữa một số tuyến cáp sao cho \(n-k\) trạm dân sự còn lại (các trạm không nằm trong danh sách trạm trọng điểm ở trên) liên lạc được với nhau.

Hãy tính tổng chi phí tối thiểu để hoàn thành loại dự án được yêu cầu.

Input

• Dòng đầu tiên chứa bốn số nguyên \(n,k,m,t\), trong đó \(n\) \((n \le 100)\) là tổng số trạm thu phát sóng, \(k\) là số lượng trạm trọng điểm, \(m\) \((m \le 1000)\) là số tuyến cáp quang, \(t=1\) ứng với dự án loại \(1\) hoặc \(t=2\) ứng với dự án loại \(2\).
• Dòng thứ hai chứa \(k\) số nguyên dương \(i_1,i_2,\ldots,i_k\) đôi một khác nhau.
• \(m\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(u_i,v_i,w_i\) thể hiện có tuyến cáp nối giữa trạm \(u_i\) và trạm \(v_i\) với chi phí sửa chữa là \(w_i\) \((w_i \le 10^6)\).

Dữ liệu đảm bảo luôn có đáp án.

Output

• In ra một số nguyên duy nhất là tổng chi phí tối thiểu để thực hiện dự án được yêu cầu.

Example

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

2

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

4

Scoring

• Subtask 1 (30% số điểm): \(t=1\) và \(k=n\).
• Subtask 2 (30% số điểm): \(t=1\) và \(k=2\).
• Subtask 3 (20% số điểm): \(t=1\) và \(2 < k \le 10\).
• Subtask 4 (20% số điểm): \(t=2\) và \(2 < k \le 10\).

Cho một xâu \(S\) gồm các ký tự ASCII nằm trên cùng một dòng.

Hãy đếm số lượng ký tự thuộc từng nhóm sau:

• Chữ cái thường: từ a đến z.
• Chữ cái hoa: từ A đến Z.
• Chữ số: từ 0 đến 9.
• Ký tự đặc biệt: các ký tự không thuộc ba nhóm trên.

Input

• Một dòng duy nhất chứa xâu \(S\) \((1 \le |S| \le 10^5)\).
• Xâu có thể chứa dấu cách và các ký tự ASCII in được từ mã 32 đến 126.

Output

In ra bốn số nguyên theo thứ tự:

• Số lượng chữ cái thường.
• Số lượng chữ cái hoa.
• Số lượng chữ số.
• Số lượng ký tự đặc biệt.

Các số được phân cách bởi một dấu cách.

Example

AbcD12#@

2 2 2 2

HelloWorld2025!

8 2 4 1

Cho một dãy số nguyên gồm \(n\) phần tử.

Bạn cần in ra các số nguyên lẻ trong dãy theo thứ tự sau:

• Trước hết là các số lẻ theo thứ tự tăng dần.
• Sau đó là các số lẻ theo thứ tự giảm dần.

Các phần tử trùng nhau vẫn được giữ nguyên. Bỏ qua tất cả các số chẵn.

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \le n \le 10^5)\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,\ldots,a_n\) \((|a_i| \le 10^9)\).

Output

• In ra một dòng gồm các số lẻ theo thứ tự tăng dần, sau đó theo thứ tự giảm dần.
• Các số được phân cách bởi một dấu cách.
• Nếu dãy không có số lẻ, in ra một dòng trống.

Example

7
1 2 3 4 5 6 7

1 3 5 7 7 5 3 1

5
10 20 30 40 50

Cho một dãy gồm \(n\) số nguyên. Sau khi sắp xếp dãy theo thứ tự tăng dần, phần tử trung vị là phần tử nằm chính giữa dãy. Trong bài toán này, \(n\) luôn là số lẻ.

Hãy tìm giá trị phần tử trung vị của dãy.

Input

• Dòng đầu tiên chứa số nguyên lẻ \(n\) \((1 \le n \le 10^5)\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,\ldots,a_n\) \((|a_i| \le 10^9)\).

Output

• In ra một số nguyên duy nhất là giá trị phần tử trung vị của dãy.

Example

5
1 5 7 2 9

5

Scoring

• Subtask 1 (30 điểm): \(1 \le n \le 100\) và \(|a_i| \le 10^3\).
• Subtask 2 (70 điểm): Không có ràng buộc bổ sung.