Vương quốc Valanro có ~N~ công trình, mỗi công trình có mã số là ~a_i~ (~1 \le i \le N~), vì muốn tối ưu hóa việc quản lý dân cư, quốc vương KaJo quyết định gộp các công trình thành ~M~ đại công trình.

• Một đại công trình sẽ được dựng lên bằng các công trình liền kề nhau (Đại công trình bao gồm tối thiểu một công trình).
• Mã số của đại công trình là ước chung lớn nhất của các mã số của các công trình trong đại công trình đó.

Xây dựng một đại công trình sẽ tốn khá nhiều công sức, vì thế quốc vương đã thỏa thuận với đội thi công như sau:

• Một đại công trình có mã số là ~K~ sẽ tốn chi phí là ~X~ để xây dựng.
• Một đại công trình có mã số khác ~K~ sẽ tốn chi phí là ~Y~ để xây dựng.

Ví dụ: Cho ~5~ công trình có các mã số là ~[8, 4, 6, 10, 14]~ cần dựng lên ~3~ đại công trình với ~K~, ~X~, ~Y~ lần lượt là ~2, 2, 3~. Dựng các đại công trình có mã số là ~[8, 2, 2]~ bằng cách gộp các công trình ~[8]~, ~[4, 6]~, ~[10, 14]~ với chi phí là ~3 + 2 + 2 = 7~.

Hãy giúp quốc vương KaJo tìm cách dựng các đại công trình có chi phí thấp nhất.

Input Format

• Dòng thứ nhất gồm ~2~ số nguyên dương ~N~, ~M~ (~N \le 10^{4}~, ~M \le min(20, N)~).
• Dòng thứ hai gồm ~3~ số nguyên dương ~K~, ~X~, ~Y~ (~K, X, Y \le 10^{9}~).
• Dòng thứ ba gồm ~N~ số nguyên dương ~a_i~ (~a_i \le 10^{9}~).

Output Format

• In ra chi phí thấp nhất để vương quốc thực hiện dự án.

Subtasks

• Có ~20\%~ số lượng test thỏa mãn điều kiện: ~N \le 10~.

• Có ~30\%~ số lượng test khác thỏa mãn điều kiện: ~N \le 2000~.

• Có ~50\%~ số lượng test còn lại thỏa mãn điều kiện: ~N \le 10^{4}~.

Sample Input 1

5 3
2 2 3
8 4 6 10 14

Sample Output 1

7

Sample Input 2

8 4
3 3 4
9 6 12 6 6 9 9 12 

Sample Output 2

13

Chiều ngày 15/05, Tổng Giám đốc VNG Corp - Ông Lê Hồng Minh và Ông Lionel Yeo - Giám đốc điều hành khu vực Đông Nam Á của ST Telemedia Global Data Centres (STT GDC), đã công bố hợp tác xây dựng và vận hành các dự án trung tâm dữ liệu mới theo tiêu chuẩn quốc tế tại TP.HCM. Quan hệ đối tác này được kỳ vọng sẽ thúc đẩy quá trình chuyển đổi số tại Việt Nam.

Trong một buổi gặp gỡ, các nhà phát triển tại trung tâm dữ liệu mới nhận được một thử thách lập trình từ Ông Lionel Yeo. Ông yêu cầu các nhà phát triển giải một bài toán liên quan đến xâu ký tự và hoán vị palindrome. Nhiệm vụ của bạn là giúp các nhà phát triển giải bài toán này.

Cho một xâu ký tự (chỉ gồm các ký tự in thường trong bảng chữ cái tiếng anh), tìm hoán vị có giá trị lớn nhất, nếu có nhiều xâu có cùng giá trị lớn nhất thì in ra xâu có thứ tự từ điển nhỏ nhất.

Lưu ý: Giá trị của hoán vị được đính nghĩa là:

• Xét các xâu con liên tiếp của hoán vị là xâu Palindrome.
• Trong các xâu đó, giá trị của hoán vị chính là độ dài của xâu con dài nhất.

Input

Một dòng duy nhất chứa xâu ~S~ ~(|S| \le 10^6)~.

Output

Xâu đáp án của đề bài.

Sample Input

baabac

Sample Output

aabcba

Note:

Giải thích: "aabcba" có xâu con palindrome dài nhất là "abcba" độ dài 5 cũng chính là đáp án tốt nhất mà chúng ta có thể tìm được.

Mô tả đề bài

Một hôm Tọi đến thăm nhà Bắp nhưng nhận thấy cô đang bận tâm về một việc gì đó. Bắp đang là một leader có tiếng trong việc quản lí team, và Bắp đang muốn chia team sao cho phù hợp.

Hiện Bắp đang có ~n~ người có số thứ tự từ ~0...n - 1~. Mỗi người trong đó đều đã được kiểm tra và đánh giá, người thứ ~i~ sẽ có performance là giá trị ~a_i~. Bắp muốn chọn ra ~3~ người trong số ~n~ người đó để lập ra ~1~ team. Với performance của ~1~ team được tính như sau: ~A * a_i + B * a_j + C * a_k~ (với ~i, j, k~ là chỉ số của ~3~ người được chọn thỏa ~0 \leq i < j < k < n~, và ~A, B, C~ là hằng số cho trước).

Tuy nhiên không phải lúc nào việc team up cũng diễn ra thuận lợi. Đôi khi ~1~ số cặp thành viên tỏ ra không ưa nhau khi ở cùng ~1~ nhóm. Bắp cũng hiểu điều này và điều tra ra được ~m~ cặp ~(x_i, y_i)~ (với ~x_i, y_i~ là chỉ số của ~n~ người trên) mà không thể chung nhóm với nhau được.

Bài toán được Bắp đặt ra như sau: hãy tính tổng performance của mọi nhóm hợp lệ có thể được tạo ra.

Input Format

• Dòng đầu tiên chứa ~4~ số nguyên dương ~n, m, A, B, C~ ~(1 \leq n, m \leq 10^5, 1 \leq A, B, C \leq 10)~
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_0, a_1, ...a_{n - 1}~ mô tả dãy số ~a~. ~(0 \leq a_i \leq 10^3)~
• ~m~ dòng tiếp theo chứa ~2~ số nguyên ~x_i, y_i~ ~(0 \leq x_i, y_i < n~ và ~x_i \neq y_i)~

Output Format

• In ra một số nguyên dương duy nhất là tổng performance của các team có thể chọn.

Subtask

• Có ~9\%~ số lượng test thỏa mãn điều kiện ~1 \leq n \leq 100~.
• Có ~18\%~ số lượng test thỏa mãn điều kiện ~1 \leq n \leq 1000~.
• Có ~73\%~ số lượng test có giới hạn như đề bài yêu cầu.

Sample Input 1

5 4 9 3 3
5 7 6 1 8 
1 2
0 2
0 2
2 3

Sample Output 1

321

Giải thích:

Các team hợp lệ có thể là:

• ~0, 1, 3~
• ~0, 1, 4~
• ~0, 3, 4~
• ~1, 3, 4~

Hai bạn A và B đang chơi trò chơi của những con số. Trò chơi bắt đầu với một con số ~S~. Mỗi vòng, A sẽ thực hiện lượt chơi trước B. Mỗi lượt chơi, người chơi có thể thay đổi con số hiện tại, gọi là ~X~, bằng một trong hai hành động sau:

• Nếu ~X~ nhỏ hơn ~9999~ thì tăng ~X~ lên một đơn vị. Ví dụ: ~X = 10~, nếu người chơi chọn hành động này thì ~X = 11~.
• Thay đổi thứ tự các chữ số của ~X~ để có được một con số khác ~X~. Ví dụ: ~X = 102~, nếu người chơi chọn hành động này thì ~X~ có thể trở thành: ~120, 12, 21, 201, 210~ (những số ~0~ đứng đầu sẽ bị loại bỏ).

Nếu đến lượt mình, người chơi không thể thực hiện hành động nào thuộc hai hành động trên thì người chơi sẽ thua.

Người thay đổi con số hiện tại thành ~F~ sẽ là người chiến thắng trò chơi.

Vì A muốn chiến thắng nên chiến thuật chơi của bạn là, nếu có thể thay đổi con số hiện tại thành ~F~ thì bạn sẽ thực hiện hành động đó, ngược lại bạn có thể chọn bất kỳ hành động nào còn lại.

Vì B là bạn thân lâu năm của A nên B muốn nhường A chiến thắng trò chơi do đó chiến thuật chơi của B là, nếu có thể B sẽ không thay đổi con số hiện tại thành ~F~ thay vào đó bạn sẽ lựa chọn những hành động khác.

Nếu A có thể chiến thắng trò chơi thì bạn có thể thắng trong ít nhất bao nhiêu vòng?

Input Format

• Dòng đầu tiên là một số nguyên ~T\ (1 \leq T \leq 30)~ thể hiện số lượng testcase.
• Ứng với mỗi testcase là hai số nguyên khác nhau ~S, F\ (0 \leq S, F \leq 9999)~.

Output Format

• Gồm ~T~ dòng, mỗi dòng là số vòng ít nhất để A chiến thắng trò chơi nếu A có thể thắng, ngược lại in ra ~-1~.

Sample Input

2
9 4
0 2

Sample Output

3
-1

Giải thích ví dụ

Testcase 1

Vòng 1:

• A chỉ có thể thực hiện hành động thay đổi ~9~ thành ~10~.
• Với ~X=10~, B có 2 thể thực hiện hành động 1 là thay đổi ~X = 10 + 1 = 11~ hoặc thực hiện hành động 2 là thay đổi ~X~ thành ~01 = 1~. B lựa chọn hành động thay đổi ~X~ thành ~1~.

Vòng 2:

• A chỉ có thể thực hiện hành động thay đổi ~1~ thành ~2~.
• B chỉ có thể thực hiện hành động thay đổi ~2~ thành ~3~.

Vòng 3:

• A thực hiện hành động thay đổi ~3~ thành ~4~ và chiến thắng trò chơi.

A đã chiến thắng trò chơi qua 3 vòng và đây cũng là số vòng ít nhất.

Testcase 2

Vòng 1:

• A chỉ có thể thực hiện hành động thay đổi ~0~ thành ~1~.
• B chỉ có thể thực hiện hành động thay đổi ~1~ thành ~2~ và chiến thắng trò chơi.

Trong trường hợp này A không thể chiến thắng.

Đây là bài tương tác, hãy đọc hướng dẫn làm bài tương tác ở đây.

Vào năm 2023, ZaloPay cho ra mắt giải pháp "Mã QR đa năng", tích hợp chuẩn VietQR. Với tính năng này, người dùng có thể thoải mái sử dụng các ứng dụng Ngân hàng hoặc Ví điện tử để thực hiện các giao dịch thanh toán một cách nhanh chóng, tiện lợi và an toàn chỉ bằng cách quét mã Zalopay QR đa năng.

Khi quét mã VietQR bằng ứng dụng ZaloPay, người dùng có thể linh hoạt sử dụng nhiều nguồn tiền khác nhau (Tài khoản tích lũy, Tài khoản trả sau, Thẻ ghi nợ/ tín dụng và tài khoản internet banking) để thực hiện chuyển tiền đến tất cả ngân hàng hỗ trợ mã VietQR.

Khi biết đến tính năng này của ZaloPay, Jug rất hứng thú và ngay lập tức tạo cho mình một mã QR đa năng bằng cách mở ứng dụng ZaloPay hoặc ZaloPay trên ứng dụng Zalo, sau đó chọn chức năng "Nhận tiền" ngay trên Trang chủ. Tiếp theo, Jug nhập số tiền là một số nguyên dương ~X~ may mắn mà anh ấy rất thích rồi tiến hành tạo mã.

Vào một ngày không trăng không sao anh đến nhà Andy và thách Andy đoán được con số ~X~ trên QR đa năng mà Jug đã tạo. Nếu đoán đúng, Andy sẽ được tặng một món quà đặc biệt từ Jug.

Cũng là một người yêu lập trình, Jug cho phép Andy hỏi bất kì câu hỏi nào liên quan đến số ~X~, miễn là sử dụng các toán tử toán học hai ngôi tồn tại trong ngôn ngữ C++, bao gồm: ~>~, ~<~, ~=~, ~+~, ~-~, ~*~, ~/~ (chia lấy nguyên), ~\%~ (chia lấy dư), ~\&~ (and), ~|~ (or), ^ (xor), ~>>~ (logical 32-bit shift right), ~<<~ (logical 32-bit shift left). Kết quả trả về sẽ có kiểu Boolean, tức là chỉ có 2 giá trị ~true~ hoặc ~false~, biết một phép toán trả về kết quả có giá trị là ~false~ nếu kết quả của phép toán trả về giá trị đúng bằng ~0~, ngược lại kết quả sẽ về ~true~. Ví dụ ~(5 - 6)~, ~(6 / 5)~ hoặc ~(1 < 2)~ sẽ trả về ~true~, nhưng ~(4 / 5)~, ~(5 - 5)~, hoặc ~(1 = 2)~ sẽ trả về ~false~.

Để đưa ra câu hỏi, Andy phải sử dụng cú pháp:

• ? <toán tử> <toán hạng>

Trong đó: toán hạng là một số nguyên không âm có giá trị không quá ~10^9~, toán tử là 1 chuỗi kí tự thuộc tập >, <, =, +, -, *, /, %, >>, <<, &, |, ^.

Chú ý, nếu phép tính gặp các lỗi như divide by zero sẽ trả về ~false~.

Ví dụ: ! < 2, ý nghĩa câu hỏi này là X < 2 trả về kết quả dưới kiểu Boolean là gì (hoặc X bé hơn 2 có đúng không).

Những câu hỏi của Andy được đánh số bắt đầu từ 1.

Tuy nhiên cuộc sống không hề đơn giản, Jug vì cố tình làm khó Andy nên đã cố tình trả lời sai ở tối đa 1 câu bất kỳ mà Andy hỏi (tức là có 0 hoặc 1 lần Jug nói dối).

Để phát hiện Jug nói dối, Andy được hỗ trợ loại câu hỏi:

• @ <toán tử> <chỉ số câu hỏi>

Trong đó: toán tử thuộc tập ~\{<,>,=\}~, ví dụ @ < 5, cho biết từ câu hỏi 1 đến 4 Jug có nói dối không? Hay @ > 5 cho biết từ câu hỏi 6 đến câu hỏi hiện tại, Jug có trả lời dối không? Chỉ được hỏi với chỉ số câu hỏi là số nguyên không âm và không vượt quá chỉ số của câu hỏi hiện tại. Lưu ý, đối với câu hỏi loại này vẫn có thể bị nói dối, và bạn không thể biết được ở tương lai có nói dối không.

Sau khi chắc ăn đoán được số X, Andy sẽ đưa ra kết quả bằng cú pháp:

• ! X

Trong đó X là một số nguyên thể hiện kết quả mà Andy đoán, sau lệnh này chương trình sẽ dừng lại và cho điểm. Câu trả lời này không tính vào số lượng câu hỏi.

Yêu cầu: Jug giữ số ~X~ có giá trị trong khoảng ~[1..10^9]~. Là một nhà lập trình tài ba, với tối đa ~100~ câu hỏi, bạn hãy giúp Andy tìm ra được số ~X~ với số lần hỏi càng ít càng tốt.

Input

Sử dụng luồng nhập xuất chuẩn để đọc các câu trả lời từ Jug.

Ở dòng đầu tiên, bạn cần đọc một số nguyên dương ~T~ (~T \le 200~), là số lượng testcase trong một test đến từ Jug.

Sau khi đọc xong ~T~, quá trình tương tác cho từng testcase sẽ bắt đầu

Interaction

Để đưa ra một câu hỏi, hãy in ra câu hỏi thuộc một trong hai dạng sau:

1. ? opt num - ~0 \le num \le 10^9~
2. @ opt idx - ~0 \le idx \le currentIndex~ với ~currentIndex~ là chỉ số của câu hỏi hiện tại.

Sau khi đưa ra câu hỏi, bạn sẽ nhận được câu trả lời dưới dạng chuỗi có giá trị "true" hoặc "false". Bạn không được hỏi quá ~100~ câu hỏi.

Để đưa ra dự đoán, hãy in ra lệnh ! X, với ~X~ là kết quả dự đoán của bạn, sau khi đưa ra lệnh này chương trình sẽ kết thúc testcase hiện tại và bắt đầu testcase tiếp theo, lệnh đưa ra kết quả này không tính vào số lượng câu hỏi.

Mỗi truy vấn in trên một dòng, và cần flush sau khi in mỗi dòng, nếu không bạn có thể sẽ nhận được thông báo ~\texttt{Time limit exceeded}~.

• ~\texttt{fflush(stdout)}~ hoặc ~\texttt{cout.flush()}~ trong C++;
• ~\texttt{System.out.flush()}~ trong Java;
• ~\texttt{flush(output)}~ trong Pascal;
• ~\texttt{stdout.flush()}~ trong Python;
• Vui lòng xem tài liệu tại đây

Tính điểm

Jug sẽ chấm điểm cho một testcase như sau, gọi ~A~ là số lượng câu hỏi bạn sử dụng để tìm ra số ~X~, ~B~ là số lượng câu hỏi được cho là tốt nhất bởi tác giả để tìm ra đáp án (trong trường hợp xấu nhất).

• ~100\%~ điểm nếu ~A ≤ B~
• ~e^{-0.05 * (A - B)} * 100\%~ điểm nếu ~A > B~, với ~e \approx 2.718281828459045~ (càng sử dụng ít câu hỏi, điểm càng cao).
• ~0\%~ nếu ~A > 100~ hoặc Andy đoán sai.

Điểm của bạn sẽ được tính bằng ~min(score_i)~, với ~score_i~ là điểm cho testcase thứ ~i~, nói cách khác, bạn sẽ được tính điểm dựa trên testcase sử dụng nhiều câu hỏi nhất. Nếu có một testcase bạn đưa ra kết quả dự đoán sai, hoặc hỏi quá ~100~ câu, sẽ nhận về ~0~ điểm.

Ghi chú

Các phép toán thực hiện trên hệ thống có thể xảy ra tràn số như một chương trình bình thường, nếu kết quả phép toán vượt quá kiểu dữ liệu int64 (số nguyên có dấu 64 bit).

Khi bạn hỏi quá ~100~ câu, hệ thống sẽ kết thúc testcase hiện tại và bắt đầu testcase tiếp theo.

Khi bạn đưa ra câu hỏi không hợp lệ, chương trình sẽ kết thúc ngay lập tức với ~0~ điểm.

Sample

Input

1
? < 5
? < 3
@ = 1
? < 1
@ < 3
? – 4
! 4

Output

true
true
false
false
true
false

Notes

Ví dụ bên trên bao gồm 1 testcase, số ~X~ cần đoán là ~4~, và Jug đã nói dối ở câu có chỉ số là ~2~.

• Ở câu hỏi đầu, ? < 5 trả về true vì 4 < 5
• Ở câu hỏi thứ 2, ? < 3 trả về false vì 4 < 3 là sai, tuy nhiên Jug đã nói dối ở câu này nên câu trả lời là true
• Ở câu hỏi thứ 3, @ = 1 trả về false vì chỉ số của câu nói dối là ~2 \neq 1~
• Ở câu hỏi thứ 4, ? < 1 trả về false vì 4 < 1 là sai
• Ở câu hỏi thứ 5, @ < 3 trả về true vì chỉ số của câu nói dối là ~2 < 3~
• Ở câu hỏi thứ 6, ? - 4 trả về false vì 4-4=0 và 0 tương đương với false
• Dòng cuối lệnh ! 4 cho biết đáp án đưa ra là ~4~, chương trình sẽ lập tức kết thúc testcase này

Ở testcase trên sử dụng tất cả ~6~ câu hỏi