Chào mừng các bạn đến với bài mở đầu, contest cuối cùng cho chuỗi Ao làng năm nay. Có lẽ loli sẽ không ra nhiều bài như trước đây nữa, nhưng vẫn luôn cố gắng đưa cho các em những bài tập chất lượng nhất để các em có thể tiếp xúc với nhiều dạng đề thú vị!

Ngoài ra các bạn có đam mê, hoài bão và có ước muốn học cao hơn, đạt giải oách hơn, giải HSG tỉnh, HSG Quốc gia, có thể tham gia vào lớp training đỉnh cao của toi hehe.

Với những lợi ích cực bú như:

• Xàm với LoliDaisukii, minh.
• Kho đề, bài tập dồi dào, chất lượng, được chọn lọc kỹ lưỡng. Là những của ngon vật lạ từ khắp bốn biển năm châu.
• Bài tập được chia thành các chủ đề nhỏ. Tất nhiên, mỗi bài tập sẽ được khầy giảng giải lại, cam kết nào hiểu thì thôi.
• Mỗi lớp sẽ có quy mô tương đối để có thể theo sát từng em, đưa ra lời khuyên, định hướng, trợ giúp riêng, giục deadline, gạ làm bài...
• Vài tuần sẽ có một contest kiểu kiểu này để các em bú tiền thưởng, cũng như để tổng hợp kiến thức.
• Chia sẻ kinh nghiệm chinh chiến.
• Cùng nhau chơi gêm, làm kèo, hóng phốt, hít hà drama, cùng làm wibu đích thực.

Lớp mở hiện tại:

1/ Cơ bản (CB)

• Hiện trong giai đoạn nước rút, đang ôn các dạng đề Tỉnh.
• Mục tiêu: Đạt giải khủng trong cuộc thi HSG cấp Tỉnh 2024-2025.

2/ Nâng cao (NC)

• Dự kiến đầu tháng 1/2025 sẽ mở lớp.
• Mục tiêu: Đội tuyển Yên Bái tham dự cuộc thi HSG Quốc gia 2025-2026. Tiện tay lấy nhẹ Nhất Tỉnh, Nhì Tỉnh..

Hình thức: Online; Bài tập: Hệ thống Codeforces riêng.

Các bạn có nhu cầu thì nhắn nhóm nhé, anh ib liền. Các em sẽ được học gia sư với giá rẻ hơn học thêm bình thường. Nếu nhắn luôn cho anh thì sẽ rep nhanh hơn hehe. Đội ngũ gia sú sẽ cam kết dạy với chất lượng tốt nhất có thể.

Quảng cáo vậy thôi, bài này nội dung thực sự được ghi sau đây.

Kết quả của các thí sinh trong một contest, ngoài yếu tố ảnh hưởng trực tiếp như đề bài, kỹ năng, code, những yếu tố khác ngoại quan như máy chấm, checker cũng ảnh hưởng ít nhiều tới số điểm cuối cùng.

Checker là đoạn chương trình chấm điểm đầu ra bài làm của thí sinh. Thông thường các bài sẽ chỉ kiểm tra xem đáp án bài làm thí sinh có trùng với đáp án cho trước, tuy nhiên một số bài toán lại có nhiều đáp án hợp lệ. Khi đó công việc của Checker là kiểm tra đầu ra của thí sinh có chuẩn xác hay không, có đáp ứng những yêu cầu của đề bài hay không. Checker như một công nhân đứng ở phía sau sân khấu, đảm bảo cho màn trình diễn của thí sinh diễn ra trơn tru. Tuy trên đề bài Checker chỉ xuất hiện bằng một dòng chữ "có thể in ra kết quả bất kỳ", nhưng đằng sau nó là hàng chục, hàng trăm dòng code, bởi bản chất, Checker cũng là một chương trình C++.

Để tôn vinh và vinh danh những cống hiến thầm lặng của Checker trong suốt chiều dài lịch sử Lập trình thi đấu, bạn hãy viết một đoạn văn thật dàiiii bằng tiếng Anh, dùng những lời có cánh với Checker, cảm ơn những công lao to lớn của Checker. Checker sẽ đọc bài viết này và đánh giá chúng trên thang điểm từ 0 đến 100.

Dùng từ càng hoa mỹ, càng được nhiều điểm. Ngoài ra nếu khen Loli xinh gái sẽ được cộng điểm.

Input

Không có input.

Output

In ra đoạn văn đáp ứng yêu cầu của đề bài. Chú ý viết bằng tiếng Anh, và toàn bộ đoạn văn đều nằm trên một dòng.

Notes

Kiểm tra kết quả chấm (Judge Feedback) để thấy nhận xét và hướng cải thiện. Hạn chế sử dụng ký tự đặc biệt, vì Checker không thể hiểu.

Số super ultra đặc biệt được định nghĩa là các số có 2 chữ số đầu bằng 2 chữ số cuối viết ngược.

Ví dụ:

• Số super ultra đặc biệt: ~1221,\ 131,\ 5,\ 66~.

• Không phải số super ultra đặc biệt: ~13,\ 31,\ 1212,\ 1231~.

Hãy đếm số lượng số super ultra đặc biệt nằm trong khoảng từ ~L~ đến ~R~.

Input

• Gồm 2 số nguyên dương ~L\ R\ (10 \le L \le R \le 10^{18})~.

Output

• In ra số nguyên duy nhất là kết quả của bài.

Scoring

• Subtask 1: 30% số test có ~L \le R \le 10^6~.

• Subtask 2: 30% số test có ~L \le R \le 10^9~.

• Subtask 3: 40% số test còn lại không có ràng buộc gì thêm.

Sample Input 1

10 100

Sample Output 1

9

Phụ hồ bao năm nay làm thợ chính, Mặc sóng gió bôn ba, ta vẫn luôn yêu đời. Bao năm lạc trôi giữa nơi, Chỉ có xi măng và cát sỏi...

Nếu các bạn chưa biết, thợ lặn VL đã có một quãng thời gian làm thợ thi công cho các công trình trọng điểm quốc gia. Trong dự án lần này, chủ đầu tư giao cho đội của anh trọng trách mông má cho công trình, cụ thể là sơn tường.

Một bản thiết kế bức tường được ship hỏa tốc đến đôi tay của anh VL. Trên bản thiết kế có ~n~ cột, mỗi cột là một mảng của tường có chiều rộng là ~1~ cm và chiều cao là khác nhau. Để công việc dễ thở hơn, anh VL đã order nóng một con lăn sơn hiệu Vương liệm, với chiều rộng của con lăn là ~x~ cm.

Khi sơn, anh VL phải để con lăn song song với mặt đất, và vừa với chiều rộng của các mảng tường, nếu không sơn sẽ bắn tùm lum và tạo thành vết bẩn. Điều này có nghĩa là anh VL phải chọn ra ~x~ mảng tường ~1~ cm liên tiếp, rồi sử dụng con lăn để sơn chúng từ dưới lên trên cùng của mảng tường thấp nhất trong một lần. Sau đó, anh ta sẽ chọn tiếp ~x~ mảng tường khác và tiếp tục lăn sơn, cho đến mảng tường cuối cùng. Vì chủ đầu tư giàu, nên anh có thể lăn sơn ở những mảng tường đã được lăn.

Như vậy, một số phần tường sẽ không được sơn, và để xử lý những phần tường này, anh ta phải dùng một cái cọ vẽ rộng ~1~ cm. Điều này chắc chắn sẽ rất mệt mỏi, nhưng so với việc bị trừ lương và bị người yêu bỏ, thì anh bắt buộc phải làm.

Các bạn hãy giúp anh VL tính phương án lăn sơn "lười" nhất có thể nhé.

Input

• Dòng đầu tiên chứa hai số nguyên ~n, x\ (1\le x \le n \le 10^6)~ – tương ứng với số mảng tường 1 cm và độ rộng của con lăn.

• Dòng thứ hai chứa dãy số nguyên dương ~h_1, h_2, \dots, h_n\ (1\le h_i < 10^7)~ – tương ứng với chiều cao của từng mảng tường.

Output

Đáp án in ra phương án lăn sơn tối ưu, bao gồm:

• Dòng đầu tiên chứa một số nguyên là diện tích tối thiểu mà VL phải sơn bằng cọ vẽ 1 cm trong phương án đó.

• Dòng thứ hai chứa một số nguyên là số lần sử dụng con lăn tối thiểu trong phương án đó.

Scoring

• Nếu chỉ in ra được diện tích tối thiểu, bạn sẽ được ~30\%~ số điểm.

• Subtask 1: ~40\%~ số điểm có ~n\le 200~.

• Subtask 2: ~40\%~ số điểm có ~n\le 10^5~.

• Subtask 3: ~20\%~ số điểm còn lại không có ràng buộc gì thêm.

Sample Input 1

5 3
5 3 4 4 5

Sample Output 1

3
2

Sample Input 2

7 4
1 2 3 4 3 2 1

Sample Output 2

4
4

Notes

Minh họa test đầu tiên, với phần gạch chéo là phần được lăn sơn:

Đặt bối cảnh Loli đang đi đu một concert, cái-mà-ai-cũng-biết ở Vinhomes Ocean Park 3. Thực ra thì concert diễn ra ở đâu Loli cũng đến và cổ vũ thôi, nhưng vì sức hút của chương trình quá đông, Loli lại không thể đặt được chỗ ngồi gần với các anh tài. Được cái, Loli chỉ thiếu vé chứ không thiếu tiền.

Chỗ ngồi ở sự kiện có dạng một lưới hình chữ nhật, với ~n~ hàng và ~m~ cột. Vị trí ở hàng ~i~ và cột ~j~ được kí hiệu ~(i,j)~. Loli dự định tiếp cận từ góc trên bên trái ~(1,1)~. Vị trí gần với các anh tài nhất nằm ở góc dưới bên phải ~(n,m)~.

Ngày diễn ra sự kiện, Loli có vẽ ra một kế hoạch thiên tài (nhắc lại, Loli chỉ vẽ thôi). Hắn sẽ lần lượt đổi chỗ của mình với người ngồi bên phải mình hoặc người bên dưới mình. Nói cách khác, nếu hắn đang ở ~(i,j)~, thì hắn có thể đổi với người ở vị trí ~(i+1,j)~ hoặc vị trí ~(i,j+1)~, miễn là vị trí đó hợp lệ.

Tất nhiên, cái gì cũng phải có cái giá của nó. Để được đổi tới vị trí mới, Loli sẽ phải trả toàn bộ phí "đổi chỗ" cho người ở vị trí mới. Nói cách khác, nếu vị trí cần tới là ~(i,j)~, thì phí cần trả là ~a_{i,j}~. Như vậy, trên đường đi vượt ngàn chông gai từ ~(1,1)~ tới ~(n,m)~, Loli sẽ phải trả tổng toàn bộ phí có trên đường đi đó (bao gồm phí ở ~(1,1)~ và ~(n,m)~).

Nhưng mà như thế thì dễ quá. Loli trong lúc hỏi giá đổi chỗ, thì có quen được một anh staff cao to đẹp trai. Anh này có đưa ra một lựa chọn rất hời nếu được sử dụng hợp lý: Với giá ~k~, anh sẽ dịch tất cả mọi người trên một hàng bất kỳ sang trái một ghế. Chi tiết hơn, nếu lựa chọn hàng ~i~, anh staff sẽ dịch người vị trí ~(i,m)~ sang ~(i,m-1)~, ~(i,m-1)~ sang ~(i,m-2)~, ..., ~(i,2)~ sang ~(i,1)~, người ở ~(i,1)~ được chuyển sang ~(i,m)~. Như vậy, phí "đổi chỗ" cũng được dịch theo tương ứng.

Loli có thể chọn dịch một hàng bất kỳ, và một hàng có thể được dịch nhiều lần, miễn là Loli trả đủ tiền cho anh staff. Tất nhiên, trước khi thực hiện phi vụ, Loli sẽ phải nói chi tiết kế hoạch dịch hàng cho anh staff. Nói cách khác, Loli không thể hú anh staff để dịch hàng khi đã ngồi xuống ghế.

Kết hợp hai thứ, các bạn có thể chỉ ra phương án cần ít vốn nhất cho Loli không?

Input

Đầu vào bao gồm nhiều test con.

Dòng đầu tiên chứa một số nguyên ~t\ (1\le t\le 10^3)~ – là số test con. Các test con có dạng sau đây:

• Dòng đầu tiên chứa hai số nguyên ~n, m\ (1\le n,m \le 360)~ – là số hàng và số cột của chỗ ngồi.

• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa ~m~ số nguyên không âm ~a_{i,1}, a_{i,2}, \dots, a_{i,m}\ (0\le a_{i,j} \le 10^9)~ – là phí "đổi chỗ".

• Dòng cuối cùng chứa một số nguyên ~k\ (0\le k\le 10^9)~ – là phí dịch hàng sang trái một ghế.

Đầu vào đảm bảo tổng số lượng vị trí (người) trong toàn bộ các test con (tổng các ~n\times m~), đều không vượt quá ~130000~.

Output

Với mỗi test con, in ra trên một dòng một số nguyên là chi phí nhỏ nhất có thể.

Scoring

• Subtask 1: ~20\%~ số điểm có đáp án tối ưu không cần dịch hàng.

• Subtask 2: ~20\%~ số điểm có ~t = 1;\ n,m \le 3~;

• Subtask 3: ~40\%~ số điểm có ~t \le 10;\ n,m \le 100~;

• Subtask 4: ~20\%~ số điểm còn lại không có ràng buộc gì thêm.

Sample Input 1

3
3 3
1 2 3
5 1 3
0 121 121
100
3 4
69 0 0 69
0 0 69 0
69 69 0 69
10
1 1
96
4

Sample Output 1

107
60
96

Notes

Ở test con thứ nhất, ta đạt được chi phí nhỏ nhất ~107~ bằng cách:

1. Dịch hàng 3 sang trái một lần. Lưới chỗ ngồi mới có phí: $$\begin{matrix}1 & 2 & 3\\5 & 1 & 3\\121 & 121 & 0\end{matrix}$$

2. Di chuyển như sau: ~(1, 1) \to (1, 2) \to (2, 2) \to (2, 3) \to (3, 3)~.

Như vậy, ta dịch hàng một lần trước khi đổi chỗ. Chi phí dịch hàng là ~k = 100~. Tổng chi phí đổi chỗ là ~1 + 2 + 1 + 3 + 0 = 7~. Tổng chi phí là ~100 + 7 = 107~.

Ở test con thứ hai, ta có thể dịch hàng 1 một lần, hàng 2 hai lần, hàng 3 ba lần. Lưới chỗ ngồi mới có phí: $$\begin{matrix}0 & 0 & 69 & 69 \\69 & 0 & 0 & 0\\69 & 69 & 69 & 0\end{matrix}$$

Tổng cộng ta dịch hàng ~6~ lần trước khi đổi chỗ. Chi phí dịch hàng là ~6\times k = 6\times 10 = 60~. Dễ thấy tồn tại cách di chuyển có chi phí ~0~. Như vậy, tổng chi phí là ~60 + 0 = 60~.

Ngân hàng dùng loại mật khẩu sử dụng một lần cho mọi truy cập tới các dịch vụ của ngân hàng.

Khi có yêu cầu truy nhập ngân hàng sẽ cung cấp một từ khóa. Người truy nhập chỉ phải nhập vào mật khẩu là một xâu ký tự palindrome độ dài dài nhất nhận được khi xóa bớt một vài ký tự trong từ khóa đã cho.

Với từ khóa đã cho hãy xác định mật khẩu cần nhập vào. Nếu tồn tại nhiều xâu khác nhau cùng thỏa mãn yêu cầu thì đưa ra xâu bất kỳ.

Input

• Gồm một dòng chứa từ khóa ~S\ (|S| \le 10^3)~ và chỉ bao gồm các ký tự la tinh thường.

Output

• In ra mật khẩu tìm được.

Scoring

• Subtask 1: 30% số điểm có ~|S| \le 16~.

• Subtask 2: 30% số điểm có ~|S| \le 100~.

• Subtask 3: 40% số điểm còn lại không có ràng buộc gì thêm.

Sample Input 1

abgeba

Sample Output 1

abgba

Sample Input 2

aaaa

Sample Output 2

aaaa