Chào mừng các bạn đến với bài mở đầu, contest mở đầu cho chuỗi Ao làng năm nay. Có lẽ anh 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ó thể nâng cao chất lượng dạy và học của tỉnh ta.

Ngoài ra các bạn có đam mê học lập trình 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 anh.

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

• 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 anh giảng giải lại, cam kết nào hiểu thì thôi.
• Mỗi lớp sẽ có quy mô nhỏ để anh 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.

Mục tiêu: Đội tuyển Yên Bái tham dự cuộc thi HSG Quốc gia 2024-2025. Tiện tay lấy nhẹ Nhất Tỉnh, Nhì Tỉnh..

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á còn 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

Dự kiến cuối tháng 5/2024 anh mở lớp, cam kết dạy từ gần như mù code đến thông thạo 7.

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

Sau những giờ code căng thẳng luôn là những giây phút giải bài tập toán hình vui vẻ!

Cho tam giác ~ABC~ nhọn ~(AB < AC)~ nội tiếp đường tròn tâm ~O~, có ba đường cao là ~AD, BE, CF~ cắt nhau tại ~H\ (D\in BC,E\in AC, F\in AB)~.

Đường thẳng ~EF~ cắt đường tròn ~(O)~ tại các điểm ~M,N~ (~M~ thuộc cung nhỏ ~AB~). Kẻ đường kính ~AK~ của đường tròn ~(O)~. Gọi chiều dài của cạnh ~KM~ là ~a~, chiều dài của ~KN~ có dạng ~x\times a~.

Tìm chiều dài của ~KN~, cụ thể là ~x~, từ đó chứng minh tam giác ~KMN~ cân tại ~K~.

Input

• Không có input.

Output

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

Loli tự hào khi có bộ sưu tập xuân hạ thu đông, gồm có ~n~ bức ảnh chụp ảnh các chị gái xinh đẹp trong anime, quả mướp ăn nướng. Mỗi bức ảnh có kích cỡ khác nhau, nhưng chúng đều là hình vuông, bức ảnh thứ ~i~ có chiều dài cạnh là ~s_i\ (cm)~.

Chẳng lẽ một bộ sưu tập đồ sộ như này lại bị chôn vùi dưới ngăn bàn suốt trăm năm? Nô nô, Loli định treo chúng lên. Mỗi bức ảnh được treo lên sẽ cần một cái khung. Bức ảnh sẽ được đặt ở chính giữa, và khung sẽ có độ rộng viền là ~w~. Mọi bức ảnh đều có viền có độ rộng giống nhau. Ví dụ: Loli có một bức ảnh ~3\times 3~, và Loli muốn viền các bức ảnh rộng ~1\ (cm)~. Vậy khung ảnh cuối cùng sẽ có kích cỡ là ~5\times 5~, và Loli cần ~25\ cm^2~ bìa để làm khung tranh đó.

Trong nhà Loli hiện có tổng ~c\ (cm^2)~ bìa (để dùng làm khung ảnh), và bằng một cách thần kỳ nào đó, chúng đã được cắt rất hợp lý để mỗi bức ảnh đều có một cái khung tương ứng, chắc là Loli đã cắt từ trước nhưng mải chơi nên quên mất. Thậm chí Loli còn quên cả độ rộng ~w~ của viền ảnh??

Yêu cầu: Tìm lại độ rộng viền ~w~ của các khung ảnh, sao cho tổng diện tích bìa của các khung ảnh bằng ~c~.

Input

• Dòng thứ nhất chứa một số nguyên ~t\ (1\le t \le 1000)~ là số test con.
• Mỗi test con đều có:
  • Dòng đầu chứa 2 số nguyên dương ~n\ (1\le n\le 2\times 10^5)~ và ~c\ (1\le c\le 10^{18})~ là số ảnh và tổng diện tích bìa.
  • Dòng thứ hai chứa ~n~ số nguyên dương ~s_i\ (1\le s_i\le 10^4)~ là chiều dài cạnh của ảnh ~i~.
• Test đảm bảo tổng số lượng ~n~ không vượt quá ~2\times 10^5~.

Output

• Gồm ~t~ dòng, dòng ~i~ chứa một số nguyên duy nhất là kết quả của test con thứ ~i~.

Subtasks

• Testcase 1: ~15\%~ số test có ~n\le 100~ và ~c\le 10^4~.
• Testcase 2: ~15\%~ số test có ~n\le 100~.
• Testcase 3: ~15\%~ số test có ~c\le 10^4~.
• Testcase 4: ~15\%~ số test có ~c\le 10^9~.
• Testcase 5: ~40\%~ số test không có ràng buộc gì thêm.

Sample Input 1

2
3 50
3 2 1
5 500
2 2 2 2 2

Sample Output 1

1
4

Giải thích:

Ở test đầu, với đáp số ~w = 1~, ta có tổng diện tích bìa là ~c = (3 + 1\times 2)^2 + (2 + 1\times 2)^2 + (1 + 1\times 2)^2 = 50~.

Ở test thứ 2, với đáp số ~w = 4~, ta có tổng diện tích bìa là ~c = (2 + 4\times 2)^2 \times 5 = 100 \times 5 = 500~.

Trong ván bài đỏ đen, khả năng thao túng quân bài là kỹ năng bá đạo và hiệu quả nhất để thay đổi vận mệnh.

Sau khi chơi thua hết xèng, Loli cực kỳ cay cú. Tuy nhiên, cô ta vẫn ở lại và chú ý xem xét và phân tích cách chia bài cũng như cách đặt bài trong mỗi một ván bài của các cao thủ võ lâm. Dường như không có sự ngẫu nhiên nào ở đây cả, cũng như chẳng có may rủi. Tất cả đều đã được tính toán.

Trong một ván bài, Loli sẽ phải solo với một đối thủ khác trong bàn. Mỗi người được đưa một bộ bài có ~n~ lá và mỗi lá bài có giá trị là một số nguyên dương, các lá đều có giá trị đôi một khác nhau.

Ban đầu, người chơi được đặt sẵn thứ tự của các lá bài trong bộ bài theo thứ tự mà người đó muốn. Sau đó tên xào bài luôn xào và phát bài cho người chơi theo cách thức sau:

• Tất cả quân bài ban đầu đều được úp xuống.
• Tên xào bài sẽ đưa cho người chơi lá ở trên cùng bộ bài (lá đầu tiên).
• Tiếp theo, hắn sẽ đặt lá ở trên cùng bộ bài lúc này xuống cuối cùng (sau lá cuối cùng).

Quá trình này lặp đi lặp lại cho đến khi bộ bài không còn bài. Người chơi sẽ tìm một dãy tăng dần liên tiếp xuất hiện trong bộ bài của mình. Sau đó dùng dãy đó để đọ với người kia, người nào có dãy dài hơn sẽ giành chiến thắng.

Loli phát hiện ra phương pháp xào bài lỏ này và muốn bạn tìm cách "thao túng" bộ bài trước khi bị xào, sao cho cổ luôn có được dãy tăng dần dài nhất có thể, để giành được chiến thắng và trả nợ hoàn lương.

Input

• Dòng đầu chứa số nguyên dương ~n\ (n \le 10^5)~,
• Dòng thứ 2 chứa ~n~ số nguyên dương ~a_i\ (a_i \le 10^9)~ là giá trị của mỗi quân bài.

Output

• ~n~ số nguyên dương là thứ tự dãy bài trước khi đưa cho tên xào bài, sao cho sau khi xào bài, ta có được dãy tăng dần liên tiếp dài nhất có thể.

Subtasks

• Subtask 1: ~20\%~ test có ~n \le 10~;
• Subtask 2: ~20\%~ test có ~n \le 100,\ a_i \le 10^4~;
• Subtask 3: ~20\%~ test có ~n \le 5000,\ a_i \le 10^4~;
• Subtask 4: ~20\%~ test có ~n \le 5000,\ a_i \le 10^9~;
• Subtask 5: ~20\%~ test không có ràng buộc gì thêm.

Sample Input 1

4
7 9 6 5

Sample Output 1

5 7 6 9

Sample Input 2

7
15 14 13 2 6 7 8

Sample Output 2

2 14 6 13 7 15 8

Giải thích:

Ở test đầu tiên, ta có dãy bài ban đầu là ~[7,9,6,5]~, đáp án là ~[5,7,6,9]~. Ta sẽ kiểm tra đáp án:

• Bộ bài hiện là ~[5,7,6,9]~.
• Đưa cho người chơi lá ~5~, cho lá ~7~ xuống cuối. Bộ bài hiện là ~[6,9,7]~.
• Đưa cho người chơi lá ~6~, cho lá ~9~ xuống cuối. Bộ bài hiện là ~[7,9]~.
• Đưa cho người chơi lá ~7~, cho lá ~9~ xuống cuối. Bộ bài hiện là ~[9]~.
• Đưa cho người chơi lá ~9~.

Dễ thấy, người chơi được nhận dãy bài ~[5,6,7,9]~, là dãy tăng dần liên tiếp dài nhất có thể.

Loli được công ty Lmao giao việc xử lý một thùng hàng có tổng khối lượng là một số nguyên dương ~n~. Loli cần phải xử lý thùng hàng đó, làm sao để chúng có được mức giá cao nhất có thể. Cách thức xử lý thùng hàng của công ty như sau:

Mỗi thùng hàng có khối lượng ~n~, và mọi số nguyên dương ~n~ đều có thể phân tích thành tích của các thừa số nguyên tố. Gọi một cách xử lý thùng hàng là một cách phân tích số ~n~ thành tích của các thừa số nguyên tố; và biểu diễn dưới dạng một chuỗi ~p~ gồm các cặp ~p_i~ có dạng ~(a, x)~.

Ví dụ: số ~100~ có thể được phân tích thành ~2^2\times 5^2~, vì vậy chuỗi ~p~ sẽ là ~[(2,2),\ (5,2)]~. Một cách xử lý khác có thể là ~10^2~, tạo ra chuỗi ~p~ là ~[(10,2)]~.

Tuy nhiên cũng có cách xử lý mà công ty không chấp nhận. Đó là những cách mà có ~a~ không phải là tích của các số nguyên tố khác nhau.

Ví dụ: số ~28~ có thể phân tích thành ~2^2\times 7^1~, vì vậy chuỗi ~p~ là ~[(2,2),\ (7,1)]~, cách xử lý này hợp lệ. Tuy nhiên một cách xử lý khác là ~4^1\times 7^1~ có chuỗi ~p~ là ~[(4,1),\ (7,1)]~ là không hợp lệ, vì có ~a=4=2\times 2~, không phải tích của các số nguyên tố khác nhau.

Một số trường hợp ~a~ không hợp lệ khác: ~12 = 2\times 2 \times 3~; ~200 = 2^3 \times 5^2~; ...

Mức giá của một cách xử lý thùng hàng chính là tổng của ~a\times x~ trong các phần tử trong chuỗi ~p~, nói cách khác, mức giá đó là ~a_1\times x_1+a_2\times x_2+\dots+a_n\times x_n~, với chuỗi ~p = [(a_1, x_1), (a_2, x_2), \dots, (a_n, x_n)]~.

Hãy tìm cách xử lý sao cho mức giá là cao nhất có thể. Chuỗi ~p~ có thể có độ dài tùy ý, miễn là cách xử lý đó hợp lệ.

Input

• Dòng đầu tiên chứa một số nguyên dương ~t\ (1\le t\le 100)~ là số test con.
• ~t~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~n\ (2\le n \le 2\times 10^9)~.

Output

• ~t~ dòng, mỗi dòng chứa một số nguyên là kết quả của bài toán tương ứng.

Subtasks

• Subtask 1: ~20\%~ test có ~n \le 15~;
• Subtask 2: ~20\%~ test có ~n \le 1000~;
• Subtask 3: ~30\%~ test có ~n \le 10^5~;
• Subtask 4: ~30\%~ test không có ràng buộc gì thêm.

Sample Input 1

3
100
10
864

Sample Output 1

20
10
22

Giải thích:

Ở test đầu, ~100 = 10^2~ nên có cách xử lý là ~p = [(10,2)]~ tạo mức giá ~10\times 2 = 20~. Cách xử lý này hợp lệ vì ~10 = 2\times 5~, là tích các số chính phương riêng lẻ. Cách xử lý ~p = [(100,1)]~ không hợp lệ vì có ~100 = 2^2 \times 5^2~, không phải tích các số chính phương khác nhau.

Ở test 2, ~10 = 10^1~ nên có cách xử lý là ~p = [(10,1)]~ tạo mức giá ~10\times 1 = 10~, hợp lệ. Cách xử lý khác là ~p = [(2,1), (5,1)]~ chỉ tạo mức giá ~2\times 1 + 5\times 1 = 7~, không phải mức giá cao nhất có thể.

Loli rất thích đến thăm bạn Shiina Mahiru - cô gái nhà bên. Vấn đề ở đây là, mặc dù là "nhà bên", nhưng nhà hai đứa lại cách nhau cả một đoạn sông. Loli vì mê gái nên tìm cách xây cả cái cầu để đi cho tiện.

Ta có thể coi đoạn sông là một cái bảng hai chiều gồm ~n~ hàng và ~m~ cột. Giao điểm của hàng thứ ~i~ và cột thứ ~j~ chứa giá trị ~a_{i,j}~ là độ sâu của ô tương ứng. Tất cả các ô ở cột đầu tiên và cột cuối cùng tương ứng với bờ sông, vì vậy độ sâu của chúng là ~0~.

Ví dụ về một đoạn sông:

Loli có thể chọn hàng thứ ~i~, chứa các ô ~(i,1),(i,2),\dots,(i,m)~ và xây cầu trên đó. Trong mỗi ô của hàng đã chọn, Loli có thể lắp đặt một trụ để đỡ cầu. Chi phí lắp đặt trụ đỡ tại ô ~(i,j)~ là ~a_{i,j}+1~.

Trụ đỡ phải được lắp đặt sao cho đáp ứng các điều kiện sau:

• Phải lắp đặt trụ đỡ tại ô ~(i,1)~;
• Phải lắp đặt trụ đỡ tại ô ~(i,m)~;
• Khoảng cách giữa bất kỳ cặp trụ đỡ liền kề nào không được vượt quá ~d~, trong đó khoảng cách giữa trụ đỡ ~(i,j_1)~ và ~(i,j_2)~ là ~|j_1-j_2|-1~.

Chỉ xây một cây cầu thì hơi dễ. Do đó, để sĩ với Mahiru, Loli sẽ xây cầu trên các hàng sông liên tiếp, tức là chọn ~i\ (1\le i \le n-k+1)~ và độc lập xây dựng cầu trên mỗi hàng ~i,i+1,\dots,i+k-1~.

Lưu ý rằng các cây cầu trên các hàng không nhất thiết phải có các trụ đỡ thẳng cột với nhau (nói cách khác, mỗi cây cầu đều được xây dựng riêng lẻ, không liên quan đến cây cầu khác).

Bạn hãy giúp Loli flex ví tiền của mình bằng cách tìm cách xây cầu tiết kiệm nhất.

Input

• Dòng đầu tiên chứa bốn số nguyên dương ~n,m,k,d~ ~(1\le k\le n\le 50,\ 3\le m\le 2\times 10^5,\ 1\le d\le m)~, lần lượt là số hàng và số cột, số cây cầu xây liên tiếp và khoảng cách tối đa giữa các trụ đỡ.
• Tiếp theo là ~n~ dòng, dòng thứ ~i~ chứa ~m~ số nguyên dương ~a_{i,j}~ ~(0\le a_{i,j}\le 10^6,\ a_{i,1}=a_{i,m}=0)~ là độ sâu của các ô sông.
• Test đảm bảo tích ~n\times m~ không vượt quá ~2\times 10^5~.

Output

• Hãy in ra một số duy nhất là tổng chi phí tối thiểu để lắp đặt trụ đỡ.

Subtasks

• Subtask 1: ~30\%~ test có ~m \le 10~;
• Subtask 2: ~30\%~ test có ~m \le 1000~;
• Subtask 3: ~40\%~ test còn lại không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

8

Giải thích:

Ở test đầu tiên:

• Để xây cầu ở hàng 1, đặt trụ ở cột ~1, 2, 4~ là tiết kiệm nhất. Chi phí là ~1 + 4 + 1 = 6~.
• Để xây cầu ở hàng 2, đặt trụ ở cột ~1, 3, 4~ là tiết kiệm nhất. Chi phí là ~1 + 2 + 1 = 4~.
• Để xây cầu ở hàng 3, đặt trụ ở cột ~1, 2, 4~ là tiết kiệm nhất. Chi phí là ~1 + 2 + 1 = 4~.
• Để xây cầu ở hàng 4, đặt trụ ở cột ~1, 2, 4~ là tiết kiệm nhất. Chi phí là ~1 + 4 + 1 = 6~.

Ta cần phải xây liên tiếp 2 cây cầu, vậy ta sẽ chọn xây ở hàng 2 và 3 sẽ là tiết kiệm nhất. Tổng chi phí là ~4+4 = 8~.