`C++`

Alice rất yêu thích các xâu kí tự. Với ba số nguyên dương `N, L, R (1 <= L <= R <= N)`, cô đã tạo ra tập `\Omega` gồm tất cả các xâu độ dài `N` là hoán vị của `N` kí tự Latin in thường đầu tiên, sao cho vị trí của kí tự `'a'` trên xâu thuộc đoạn `[L; R]` (vị trí của các ký tự trong xâu được đánh số từ `1` đến `N`).

Bob muốn tạo ra một xâu `U` chứa tất cả các xâu trong tập `\Omega` và có độ dài càng nhỏ càng tốt. Ở đây, xâu `X` được gọi là chứa xâu `Y` nếu như có thể xóa bỏ một số ký tự của xâu `X` (có thể không xóa ký tự nào) và giữ nguyên thứ tự của các ký tự còn lại để có được xâu `Y`.

Tuy nhiên, Alice đã không cho Bob biết chính xác giá trị của `N, L, R`. Thay vào đó, cô sẽ trả lời một số câu hỏi của anh. Với mỗi lần hỏi của Bob:

• Bob sẽ đưa cho Alice một xâu `s` có độ dài không quá `200`. Xâu này chỉ được chứa các ký tự Latin in thường.

• Alice sẽ tính toán và trả lời cho Bob biết số xâu `t in \Omega` thỏa mãn xâu `s` khớp với xâu `t` chia lấy dư cho `379`.

Sau khi hỏi Alice một số câu hỏi, Bob sẽ trả lời xâu `U` mà anh tìm được. Để thể hiện sự thông minh của mình trước Alice, Bob muốn giá trị `P = Q + |U|` càng nhỏ càng tốt, trong đó `Q` là số câu hỏi Bob đã thực hiện và `|U|` là độ dài xâu `U` mà Bob trả lời. Hãy lập trình giúp Bob một chương trình tương tác với Alice để thực hiện yêu cầu trên.

Chi tiết cài đặt

Thí sinh cần cài đặt hàm sau:

$\texttt{string solve()}$

• Hàm này có thể được gọi nhiều lần bởi trình chấm.

• Hàm này cần trả về xâu `U` thỏa mãn điều kiện đề bài. Lưu ý là bạn không được biết trước giá trị của `N, L, R`.

Trong hàm solve(), thí sinh được phép gọi hàm sau (thí sinh cần khai báo trước thư viện smatchlib.h để có thể sử dụng hàm này):

$\texttt{int ask(string s)}$

• `s`: Xâu mà Bob sẽ đưa cho Alice để thực hiện câu hỏi. Xâu `s` chỉ được chứa các ký tự Latin in thường và có độ dài không quá `200`.

• Hàm sẽ trả về một số nguyên không âm là số lượng xâu `t` thuộc `\Omega` thỏa mãn `s` khớp với `t` chia lấy dư cho `379`.

Ngoài ra, thí sinh được phép cài đặt các biến, các hàm toàn cục, nhưng không được phép có hàm main().

Cách cài đặt và trình chấm ví dụ có thể xem tại contest material, lưu ý trình chấm ví dụ chỉ mô phỏng cách hoạt động và sẽ không được dùng để chấm chính thức.

Ràng buộc

• `4 <= N <= 13`

• `1 <= L <= R <= N`

Trình chấm của bài này không mang tính thích ứng. Điều này tương đương với việc các giá trị `N, L, R` sẽ được cố định từ đầu và không thay đổi trong suốt quá trình chương trình của bạn tương tác với trình chấm.

Scoring (như hình)

Cách tính điểm

Giả sử test có tối đa `1` điểm. Nếu trong bất kỳ lần gọi hàm solve nào, xâu `U` bạn đưa ra không thỏa mãn với điều kiện của đề bài thì bạn sẽ được `0` điểm cho toàn bộ test đó. Ngược lại, điểm của bạn sẽ được tính như sau:

• Mỗi lần gọi hàm solve sẽ có điểm của lần gọi hàm đó (gọi là score). Xét lần gọi hàm tương ứng, gọi giá trị `P = Q + |U|` là độ tối ưu kết quả của thí sinh, giá trị `J = Q + |U|` là độ tối ưu kết quả của bạn tổ chức (`Q` là tổng số lần thực hiện truy vấn ask, `U` là xâu đáp án trả về đã thỏa mãn điều kiện). Khi đó:

• Nếu `Q > 10` thì score `= 0`.

• Nếu `P - J > N` thì score `= 0.4 * 0.9^(P - J - N - 1)`

• Nếu `4 <= P - J <= N` thì score `= 0.4 + 0.4 * 0.8^(P - J - 4)`

• Nếu `0 < P - J < 4` thì score `= 0.8 + 0.2 * 0.8^(P - J)`

• Nếu `P <= J` thì score `= 1`

• Điểm của một test sẽ bằng điểm (giá trị score) nhỏ nhất trong tất cả lần gọi hàm solve.

Điểm của mỗi subtask là điểm thấp nhất của một test trong subtask đó nhân với số điểm tối đa của subtask.

Sample Grader

Trình chấm mẫu đọc dữ liệu vào theo định dạng sau:

• Dòng 1: N L R

Trình chấm mẫu sẽ in ra một trong các kết quả sau:

• Example passed! nếu như xâu U do chương trình của bạn đưa ra thỏa mãn yêu cầu đề bài.

• Wrong answer! nếu như xâu U do chương trình của bạn đưa ra không thỏa mãn yêu cầu đề bài.

• Invalid operation! nếu như chương trình của bạn gọi hàm ask() không hợp lệ.