Trung tâm lái xe tổ chức một đợt sát hạch vào lúc 8 giờ 00 phút sáng. Thời gian thực hiện bài sát hạch tối đa là 100 phút. Đợt sát hạch gồm \(N\) thí sinh được đánh số từ 1 đến \(N\). Thí sinh thứ \(i\) hoàn thành bài sát hạch trong \(T_i\) phút (\(1\le i \le N\)).

Yêu cầu: Hãy lập trình đưa ra thời điểm kết thúc bài sát hạch của mỗi thí sinh giúp trung tâm.

Input: Dữ liệu vào từ tệp văn bản TG.INP

• Dòng đầu tiên chứa một số nguyên \(N\) là số lượng thí sinh (\(1 \le N \le 20\)).
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa một số nguyên \(T_i\) là thời gian hoàn thành bài sát hạch của thí sinh thứ \(i\) (\(0 \le T_i \le 100,1\le i \le N\)).

Output: Ghi ra tệp văn bản TG.OUT

• Gồm \(N\) dòng, mỗi dòng là thời điểm bài sát hạch kết thúc của từng thí sinh có cấu trúc giờ phút (không chứa dấu cách). Nếu giờ và phút nhỏ hơn 10 thì ghi thêm một chữ số 0 trên đầu (ví dụ: 8 giờ 5 phút viết là 08:05).

Example

3
5
10
65

08:05
08:10
09:05

Cho một tờ giấy hình chữ nhật kích thước \(M(cm) \times N(cm)\) và một số tự nhiên \(K\).

Yêu cầu

Nếu cắt những hình vuông có kích thước \(K(cm) \times K(cm)\) từ tờ giấy này thì diện tích còn lại nhỏ nhất là bao nhiêu \(cm^2\)?

Dữ liệu đầu vào

Gồm ba số tự nhiên \(M, N, K\) lần lượt mỗi số trên một dòng \((1 \le M, N, K \le 10^9)\).

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là kết quả của bài toán.

Ví dụ

8
7
3

20

Một mật thư chứa mật mã bí ẩn được tạo ra là một xâu kí tự chỉ gồm các chữ số và các kí tự in thường. Mật mã bí ẩn là số lượng các số nguyên phân biệt xuất hiện trong thư.

Ví dụ: Với mật thư as00023dkrf23smk1asd23sam09aa9 chứa \(3\) số nguyên phân biệt \(23, 1, 9\). Nên mật mã là \(3\).

Dữ liệu nhập vào từ file văn bản MM.INP:

• Một xâu (độ dài xâu ≤ 100) gồm các chữ số và các kí tự in thường. Tất cả các số nguyên trong xâu có nhiều nhất 3 chữ số.

Kết quả ghi ra file văn bản MM.OUT:

• Một số nguyên duy nhất là kết quả của bài toán.

Example

abc123abc2a3a1

4

as00023dkrf23smk1asd23sam09aa9

3

Cho mạch mã gốc DNA bốn loại nucleotide A, T, G, C. Để tiết kiệm bộ nhớ, mạch mã gốc đã được nén lại thành một chuỗi \(S\) gồm các cặp là số lần xuất hiện liên tiếp nucleotide và loại nucleotide tương ứng.
Ví dụ Mạch mã gốc AAACAATGGGGA nén thành 3A1C2A1T4G1A.
Các nucleotide ở hai mạch của phân tử DNA liên kết với nhau theo nguyên tắc bổ sung, trong đó A liên kết với T, G liên kết với C. Do vậy, nếu biết trình tự nucleotide trên một mạch có thể suy ra trình tự của mạch còn lại.
Ví dụ Một đoạn phân tử DNA ở sinh vật nhân thực có trình tự nucleotide trên mạch mã gốc là AAACAATGGGGA. Trình tự nucleotide trên mạch bổ sung của đoạn DNA này là: TTTGTTACCCCT

Yêu cầu

Cho một chuỗi ký tự \(S\) mô ta mạch mã gốc DNA sau khi đã nén. Hãy lập trình xác định mạch bổ sung của mạch mã gốc sau khi nén.

Dữ liệu đầu vào

Một chuỗi \(S\) có độ dài không vượt quá \(1000\). Dữ liệu đảm bảo chuỗi sau khi giải nén có độ dài không vượt quá \(10^5\).

Dữ liệu đầu ra

Gồm chuỗi ký tự là mạch bổ sung của mạch mã gốc sau khi nén.

Ràng buộc dữ liệu

• Có 20% số test ứng với 20% số điểm của bài thỏa mãn: độ dài chuỗi \(S\) là \(2\), trong đó ký tự đầu tiên là chữ số, ký tự thứ hai là một trong 4 chữ cái là A, T, G, C;
• Có 20% số test khác ứng với 20% số điểm của bài thỏa mãn: có duy nhất một loại nucleotide;
• Có 40% số test khác ứng với 40% số điểm của bài thỏa mãn: số lần xuất hiện liên tiếp nucleotide A, T, G, C nhỏ hơn 10;
• Có 20% số test còn lại ứng với 20% số điểm không có ràng buộc gì thêm.

Ví dụ

5A2G1A11T1C

TTTTTCCTAAAAAAAAAAAG

Để trang trí Tết, Nam treo một dây đèn gồm \(N\) bóng đèn, được đánh số từ \(1\) đến \(N\), từ trái sang phải. Mỗi bóng đèn khi bật sẽ có hai màu vàng hoặc đỏ. Dây đèn được nhúng một mã lệnh cho phép nhận một số tự nhiên \(X\). Khi đó, màu của bóng đèn thứ \(X\) và các bóng đèn cách bóng đèn thứ \(X\) không quá \(K\) bóng đèn sẽ đều đổi từ vàng thành đỏ hoặc ngược lại.
Ban đầu các bóng đèn đều có màu vàng. Để dây đèn trông đẹp mắt, Nam đã lập trình để điều khiển màu của các bóng đèn. Chương trình của Nam có \(M\) dòng lệnh, mỗi dòng lệnh tương ứng với một lần gọi mã lệnh của dây đèn. Vì số lượng bóng đèn quá lớn, sau khi lập trình xong, Nam muốn kiểm tra ngẫu nhiên màu một số bóng đèn xem có đúng như ý tưởng ban đầu không.

Yêu cầu

Cho các số tự nhiên \(X\) là tham số của \(M\) dòng lệnh trong chương trình của Nam. Hãy lập trình để trả lời \(Q\) câu hỏi tương ứng với các lần kiểm tra của Nam. Biết rằng mỗi câu hỏi chứa một số nguyên dương \(P\) để xác định xem bóng đèn thứ \(P\) trong dây đèn có màu vàng hay đỏ.

Dữ liệu đầu vào

• Dòng đầu tiên gồm bốn số nguyên dương lần lượt là \(N, M, Q, K (1 \le N \le 10^9; 1 \le M \le 10^5; 1 \le Q \le 10^5; 0 < K \le N)\);
• Dòng thứ hai gồm \(M\) số nguyên dương \(X_i\) mô tả tham số của lệnh thứ \(i (1 \le X_i \le N)\);
• Dòng thứ ba gồm \(Q\) số nguyên dương \(P_i\) mô tả câu hỏi thứ \(i (1 \le P_i \le N)\).

Dữ liệu đầu ra

• Gồm \(Q\) dòng, dòng thứ \(i\) là câu trả lời cho câu hỏi thứ \(i\). Nếu bóng đèn tại vị trí \(P_i\) đang có màu vàng thì ghi ra ký tự \(V\), ngược lại ghi ra kí tự \(D\).

Ràng buộc dữ liệu

• Có 60% số test ứng với 60% số điểm của bài thỏa mãn: \(N, M, Q \le 10^3\);
• Có 20% số test ứng với 20% số điểm của bài thỏa mãn: \(N, M \le 10^5\);
• Có 20% số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm

Ví dụ

7 2 4 1
3 5
2 7 4 5

D
V
V
D

Nguồn: Học sinh Giỏi THCS Hà Nội năm 2022 - 2023

Các trạm thu, phát sóng viễn thông của thành phố được đặt trên một đường tròn. Đường tròn này được chia thành \(10^6\) điểm cách đều nhau theo chiều kim đồng hồ. Một vị trí trên đường tròn được chọn là mốc 0. Có \(N\) trạm thu sóng được đánh thứ tự từ 1 đến \(N\), trạm thứ \(i\) đặt ở vị trí \(a_{i}\) (\(1 \le i \le N\)).

Thành phố dự kiến sẽ đầu tư \(K\) trạm phát sóng với phạm vi phát như nhau. Tuy nhiên, một trạm phát sóng với phạm vi phát càng dài thì chi phí càng cao. Vì vậy, thành phố cần tính toán để đầu tư các trạm phát sóng có phạm vi phát ngắn nhất và phải đảm bảo các trạm thu sóng đều nhận được tín hiệu.

Khi một trạm phát sóng có phạm vi phát là \(R\) thì các trạm thu sóng trong khoảng cách \(R\) theo cả hai chiều kim đồng hồ đều nhận được tín hiệu. Ví dụ: Trạm phát sóng tại vị trí \(3\) với phạm vi phát 1 thì cả trạm thu sóng ở vị trí \(2\) và \(4\) đều nhận được tín hiệu.

Yêu cầu: Tìm phạm vi phát ngắn nhất của \(K\) trạm phát sóng sẽ đầu tư để \(N\) trạm thu sóng đều nhận được tín hiệu.

Input

Dữ liệu vào từ tệp văn bản TPS.INP:

• Dòng đầu tiên chứa số nguyên dương \(N\) (\(1 \le N \le 10^3\)).
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa một số nguyên \(a\), là vị trí trạm thu sóng thứ \(i\). Không có hai trạm nào cùng vị trí (\(0 \le a_i < 10^6,1\le i\le N\)).
• Dòng cuối cùng chứa số nguyên \(K\) là số trạm phát sóng (\(1 \le K <N\)). Chú ý, vị trí trạm phát có thể được đặt cùng vị trí của một trạm thu nào đó.

Output

Kết quả ra tệp văn bản TPS.OUT:

• Số nguyên duy nhất là phạm vi phát sóng ngắn nhất của \(K\) trạm phát.

Examples

4
5
1000 
12345
987
2

498

Note

• Đặt một trạm phát sóng ở vị trí \(503\) và một trạm phát sóng ở vị trí \(12340\) có phạm vi phát sóng là \(498\).

2
1
999999
1

1

Note

• Đặt một trạm phát sóng ở vị trí \(0\) có phạm vi phát sóng là \(1\).