Một xâu ~S~ được gọi là xâu đối xứng nếu ~S = S'~ với ~S'~ là xâu nhận được từ xâu ~S~ khi đọc từ phải qua trái. Ví dụ: Xâu ~'aba'~ là xâu đối xứng, còn xâu ~'abc'~ là xâu không đối xứng.

Cho một xâu ~S~ gồm ~1 \le n \le 1000~ kí tự.

Yêu cầu: Hãy tìm cách chia xâu ~S~ thành ít nhất các đoạn mà mỗi đoạn đều là các xâu đối xứng.

Input

• Dòng đầu gồm một số nguyên ~n~ là độ dài của xâu ~S~.
• Dòng thứ hai là nội dung xâu ~S~.

Output

• Dòng đầu ghi một số nguyên ~k~ (số đoạn ít nhất tìm được).
• ~K~ dòng sau, mỗi dòng ghi một số nguyên ~t_i~, với ~t_i~ là vị trí kết thúc của đoạn thứ ~i~.

Sample Input 1

 8
 abbacdcb

Sample Output 1

3
4
7
8

Cho một số nguyên dương ~n~, hãy phân tích số ~n~ thành tổng của một số số nguyên dương sao cho bội chung nhỏ nhất của chúng là lớn nhất có thể.

Input

• Gồm một số nguyên dương ~n~, ~(1 \le n \le 340)~

Output

• In ra bội chung nhỏ nhất tìm được.

Sample Test

Input:

10

Output:

30

Giải thích: Số ~10~ được phân tích thành tổng của ~3~ số ~{2,3,5}~, bội chung nhỏ nhất của ba số đó bằng ~30~, đây là kết quả lớn nhất có thể.

Các nghiện thủ đang bị nhốt trong căn phòng có 1 mật mã được mã hóa trong mảng ~A~ có độ dài ~n~. Bởi muốn nghiện Liên Quân, thần đồng đã sai người tìm và giải mã nó. Ta biết được mảng ~A~ có thể chia thành nhiều dãy con liên tiếp (và có ~2^{n-1}~ cách chia ). Với mỗi dãy con được chia, giá trị của dãy con đấy nếu gồm các số từ vị trí ~l~ đến ~r~ là :

• ~r \;– \; l + 1 ~ nếu tổng các số từ ~l~ đến ~r~ lớn hơn hẳn 0.
• 0 nếu tổng các số từ ~l~ đến ~r~ bằng 0.
• ~–(r \;– \; l + 1)~ nếu tổng các số từ ~l~ đến ~r~ nhỏ hơn hẳn 0.

Gọi ~S~ là tổng các giá trị của dãy con trong 1 cách chia. Mã hóa của căn phòng là ~S~ lớn nhất trong tất cả các cách chia. Biết rằng tin Ams 21-24 toàn những feeder liên quân và best tin học, thần đồng muốn nhờ các bạn tìm mật mã trên.

Input

• Dòng đầu tiên gồm số ~n~
• Dòng tiếp theo gồm ~n~ số của mảng ~A~

Output

• In ra một số là giá trị ~S~ lớn nhất tìm được.

Sample Test

Input:

5
-1 -2 3 -1 -1

Output

1

Sample Test 2

Input:

6
-1 2 -3 4 -5 6

Output

6

Sample Test 3

7
1 -1 -1 1 -1 -1 1

Output

-1

Giải thích:

• Test 1 chia thành (-1 -2 ) (3 -1 -1)
• Test 2 chia thành (-1 2 -3 4 -5 6)
• Test 3 chia thành (1 -1 -1 1 -1) (-1 1)

Ràng buộc:

• ~A_i \le 10^9~
• Subtask 1: ~n \le 20~ (30%)
• Subtask 2: ~n \le 5000~ (40%)
• Subtask 3: ~n \le 5*10^5~ (30%)

Một xí nghiệp có một robot dùng để xếp các sản phẩm vào các thùng. Mọi thùng đều có dung tích như nhau. Có đúng hai thùng đang mở sẵn để robot xếp các sản phẩm vào. Mỗi thùng bất kỳ đều chứa được số sản phẩm mà tổng dung tích của chúng không vượt quá dung tích của thùng. Robot có thể thực hiện các thao tác sau:

• Đưa một sản phẩm hiện tại trên dãy băng vào thùng ~1~,
• Đưa một sản phẩm hiện tại trên dãy băng vào thùng ~2~,
• Đóng thùng ~1~ và mở một thùng mới thay thế cho thùng ~1~,
• Đóng thùng ~2~ và mở một thùng mới thay thế cho thùng ~2~.

Các thao tác 1, 2 chỉ có thể thực hiện nếu tổng dung tích của sản phẩm cho vào và các sản phẩm đã có trong thùng không vượt quá dung tích của thùng.

Yêu cầu: Cho biết dung tích mỗi thùng là ~𝑊~, dung tích của ~𝑛 sản~ phẩm trên dãy băng theo thứ tự xuất hiện là ~𝑎_1, 𝑎_2, . . . , 𝑎_𝑛~ , hãy tìm số thùng ít nhất để có thể cho ~𝑛~ sản phẩm vào thùng.

Input

• Dòng thứ nhất là hai số nguyên ~𝑊~ và ~𝑛~;
• Dòng tiếp theo chứa các số mô tả các số ~𝑎_1, 𝑎_2, … , 𝑎_𝑛~.

Output

• Gồm một số duy nhất là số thùng ít nhất cần dùng.

Input

8 6
4 2 5 3 5 4

Output

3

Giải thích

• Đưa ~1~ vào thùng ~1~
• Đưa ~2~ ~3~ ~4~ ~5~ vào thùng ~2~ (cần mở thêm một thùng)
• Đưa ~6~ vào thùng ~1~ (vẫn còn đủ chỗ, không cần mở thêm)

Ràng buộc

• Subtask 1 [10 tests] ~𝑊 ≤ 10^9 ; 𝑛 ≤ 20~
• Subtask 2 [10 tests] ~1 ≤ 𝑎_𝑖 ≤ 2; 𝑊 = 100; 𝑛 ≤ 10^6~
• Subtask 3 [10 tests] ~𝑊 ≤ 30; 𝑛 ≤ 10000~
• Subtask 4 [10 tests] ~𝑊 ≤ 5000; 𝑛 ≤ 100~
• Subtask 5 [10 tests] ~𝑊 ≤ 5000 ; 𝑛 ≤ 10000~

Tỉ phú Vương dự định sẽ xây một thủy cung thu hút khách du lịch. Để thực hiện dự định đó, ông ta đã mua ~n~ chú cá và ~m~ bể thủy sinh. Chú cá thứ ~i~ có sức mạnh là ~a_i~

Vương cần phải quyết định xem, với mỗi chú cá thì ông sẽ đặt vào bể thủy sinh nào. Tuy nhiên, việc này không hề đơn giản, khi ông sẽ phải xem xét đến giới hạn không gian và khả năng kìm hãm sự phát triển lẫn nhau giữa những chú cá trong cùng một bể. Sau những tính toán kĩ lưỡng, ông đã ước tính rằng mức độ bất ổn của mỗi chú cá sẽ bằng tổng sức mạnh của các chú cá nằm cùng bể thủy sinh với chú cá đó (bao gồm cả bản thân chú cá đó).

Yêu cầu: Hãy giúp tỉ phú Vương đặt các chú cá vào các bể thủy sinh sao cho tổng độ bất ổn của các chú cá là nhỏ nhất.

Input

• Dòng đầu tiên gồm hai số nguyên ~n~ và ~m~ ~(1 \le m \le n \le 2000)~ cho biết số chú cá và số bể thủy sinh.
• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, . . . , a_n (1 \le ai \le 10^9 )~ cho biết sức mạnh của các chú cá.

Output

• In một số nguyên duy nhất là tổng độ bất ổn nhỏ nhất của các chú cá.

Subtask

• Có ~20\%~ số test ứng với ~n \le 8~.
• Có ~20\%~ số test khác ứng với ~n \le 15~.
• Có ~20\%~ số test khác ứng với ~m = 2~.
• Có ~30\%~ số test khác ứng với ~n \le 100~.
• ~10\%~ số test còn lại không có giới hạn gì thêm.

Sample Input 1

6 3
9 2 11 3 5 8

Sample Output 1

75

Sample Input 2

4 4
10 20 30 40

Sample Output 2

100

Explanation

Trong ví dụ thứ nhất, một cách đặt cá vào bể thủy sinh tối ưu như sau:

• Đặt chú cá thứ ~1, 6~ vào bể thứ nhất.
• Đặt chú cá thứ ~2, 4, 5~ vào bể thứ hai.
• Đặt riêng chú cá thứ ~3~ vào bể thứ ba. Độ bất ổn của các chú cá lần lượt là ~17 + 10 + 11 + 10 + 10 + 17 = 75~.

Ở ví dụ thứ hai, ta sẽ đặt riêng mỗi chú cá vào một bể thủy sinh.

Cho một đa giác lồi gồm ~n~ đỉnh trên hệ trục tọa độ ~OXY~. Các điểm được đánh số từ ~p_1,p_2,...,p_n~.

Với mỗi điểm ~p_i~ ~(1 \le i \le n)~, hãy xác định chu vi lớn nhất của lục giác gồm các điểm trên đa giác và chứa điểm ~i~.

Input

• Dòng đầu gồm số nguyên dương ~n~.
• ~n~ dòng sau, dòng thứ ~i~ gồm ~2~ số nguyên dương ~x_i,y_i~ miêu tả tọa độ của điểm thứ ~i~. Các điểm được cho theo chiều ngược kim đồng hồ.

Output

• Gồm ~n~ dòng, dòng thứ ~i~ in ra chu vi lớn nhất của lục giác gồm các điểm trên đa giác và chứa điểm ~i~. Kết quả làm tròn đến số thứ ~4~ sau dấu phẩy.

Constraints .

• ~1 \le n \le 1000~.
• ~|x_i|,|y_i| \le 10^9~.

Subtask

• Sub ~1~ (~30\%~): ~n \le 10~.
• Sub ~2~ (~30\%~): ~n \le 100~.
• Sub ~3~ (~40\%~): ~n \le 1000~.

Sample Input 1

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

Sample Output 1

27.3183
26.8052
27.3183
27.3183
27.2445
27.3183
27.3183
27.3183

Nhân dịp khánh thành siêu thị VINCOMPLAZA tại Đông Hà, Việt Anh được bố mẹ dẫn đi chơi tại khu vui chơi có trong siêu thị. Bạn ấy rất thích thú với các trò chơi ở đây, đặc biệt là trò chơi mang tên "G_SCORES" với hệ thống tính điểm vô cùng thú vị.

G_SCORES là trò chơi mới được các nhà phát triển tạo ra ~N~ màn chơi, màn chơi thứ ~i~ có cấp độ là ~i~. Hệ thống điểm thưởng cho các cấp độ của trò chơi được thiết lập như sau:

• Cấp độ ~i~ có điểm thưởng là số nguyên dương ~s_i~ có giá trị từ ~1~ đến ~N~. Các cấp độ được sắp xếp theo độ khó tăng dần ~(s_1 \leq s_2 \leq \ldots \leq s_n)~;

• Để đảm bảo người chơi vượt qua nhiều cấp độ sẽ được xếp hạng cao hơn, các nhà phát triển thiết lập quy tắc: Với một số ~k~ ~(2 \leq k \leq N)~ bất kỳ, tổng số điểm của ~k~ màn chơi phải lớn hơn tổng số điểm của mọi lần mà có số màn chơi ít hơn ~k~.

Yêu cầu: Cho ~N~ màn chơi, hỏi có bao nhiêu cách thiết lập hợp lệ để các nhà phát triển thiết lập hệ thống điểm cho các cấp độ thỏa mãn những điều kiện nêu trên?

Input

Vào từ tệp văn bản SCORES.INP có cấu trúc sau:

• Dòng đầu tiên chứa một số nguyên ~T~ ~(1 \leq T \leq 5)~ là số lượng bộ tests;

• ~T~ dòng tiếp theo, dòng thứ ~i~ chứa số nguyên ~N (2 \leq N \leq 5000)~ là số màn chơi.

Output

Ghi ra vào tệp SCORES.OUT gồm có ~T~ dòng, dòng thứ ~i~ theo thứ tự ghi phần dư của số cách thiết lập hệ thống điểm hợp lệ khi chia ~10^9 + 7~

Scoring

Sample Input 1

3
2
3
4

Sample Output 1

3
7
16

Notes

Ở ví dụ trên với ~N = 3~ ta có ~7~ dãy ~s_i~ tương ứng như sau:

• ~1 \space 1 \space 1~

• ~1 \space 2 \space 2~

• ~1 \space 3 \space 3~

• ~2 \space 2 \space 2~

• ~2 \space 2 \space 3~

• ~2 \space 3 \space 3~

• ~3 \space 3 \space 3~

Một cánh đồng lúa hình chữ nhật có kích thước chiều dọc là ~L~ và chiều ngang là ~W~ cần được đào ~m~ đường mương khác nhau chạy song song với cạnh chiều ngang nối hai cạnh chiều dọc của cánh đồng nhằm phục vụ hiệu quả cho việc tưới tiêu canh tác. Các đường mương này chia cánh đồng theo chiều dọc thành ~(m+1)~ lớp có diện tích dương. Trong bài toán này, chúng ta coi mỗi đường mương có bề rộng không đáng kể.

Chính quyền địa phương tìm các phân chia cánh đồng lúa cho ~n~ hộ gia đình quản lý canh tác, hộ gia đình thứ ~i~ được chia một thửa ruộng hình chữ nhật con nằm trong một lớp có hai cạnh thuộc đường mương hoặc cạnh chiều ngang của cánh đồng, và có diện tích định trước ~a_i~ sao cho ~\sum{a_i}=L \cdot W~. Gọi ~l_i~ và ~w_i~ lần lượt là kích thước chiều dọc và chiều ngang thửa ruộng của hộ gia đình thứ i, chu vi thửa ruộng là ~p_i = 2 \cdot (l_i + w_i)~. Chính quyền địa phương mong muốn tìm ra phương án phân chia sao cho tổng chu vi tất cả các thửa ruộng con ~\sum{p_i}~ là nhỏ nhất.

Yêu cầu: Cho biết kích thước chiều dọc ~L~ và chiều ngang ~W~ của cánh đồng lúa hình chữ nhật, số lượng mương cần đào và n giá trị diện tích ~a_1, a_2, ..., a_n~. Hãy giúp chính quyền địa phương tìm ra phương án phân chia mong muốn và đưa ra giá trị tổng chu vi nhỏ nhất của tất cả các thửa ruộng con.

Input

Đọc từ thiết bị vào chuẩn:

• Dòng đầu tiên chứa một số nguyên dương ~T~ là số lượng bộ test ~(T \le 3)~

• Mỗi nhóm dòng trong số T nhóm dòng tiếp theo mô tả một bộ test có cấu trúc như sau:

  — Dòng thứ nhất chứa hai số nguyên không âm ~n~ và ~m~ ~(m < n \le 25000)~.

  — Dòng thứ hai chứa hai số nguyên không âm ~L~ và ~W~ ~(L, W \le 10^9)~.

  — Dòng cuối cùng chứa ~n~ số nguyên dương ~a_i (a_i \le 10^9, 1 \le i \le n)~. Dữ liệu đảm bảo ~\sum{a_i}=L \cdot W~.

Hai số liên tiếp trong cùng một dòng được ghi cách nhau bởi dấu cách.

Output

Ghi ra thiết bị ra chuẩn ~T~ dòng, mỗi dòng một số thực duy nhất là tổng chu vi tính được trong bộ test tương ứng và có tối đa ~9~ chữ số sau dấu chấm thập phân. Đáp án của bạn được phép có sai số tuyệt đối đến ~10^{-3}~ so với đáp án trong bộ test.

Scoring

Sample Input 1

1
7 2
7 8
11 7 12 6 3 7 10

Sample Output 1

80.000000000