Công ty xổ số Lottery vừa ra mắt một mô hình xổ số mới. Ban đầu họ chọn và công bố hai số nguyên dương ~n~ và ~k~. Một xâu nhị phân ~s~ có độ dài ~n~ được chọn để làm giải độc đắc và được giữ bí mật. Hình thức bán vé của công ty là cho phép người chơi chọn số nhị phân (hoặc ~0~ hoặc ~1~) ở một số vị trí trong số ~n~ vị trí trên tấm vé và bỏ trống các vị trí còn lại. Tấm vé sau đó được in ra có mã số là một xâu có độ dài ~n~ và chỉ chứa các kí tự '0', '1', '*' mô tả các vị trí bỏ trống. Việc bỏ trống một số vị trí sẽ tăng khả năng trùng khớp với giải độc đắc, tuy nhiên, cũng làm tăng giá của tấm vé số lên. Cụ thể, giá của một tấm vé có mã số ~t~ được tính như sau:

• Gọi ~a~, ~b~, ~c~ lần lượt là số lượng kí tự '0', '1', '*' trên xâu ~t~;

• Giá của tấm vé sẽ là ~a + b + 2c~;

và độ trùng khớp của tấm vé này với giải độc đắc được tính như sau:

• Đánh số các kí tự trên ~s~ từ ~0~ đến ~n - 1~ từ trái sang phải;

• Đánh số các kí tự trên ~t~ từ ~0~ đến ~n - 1~ từ trái sang phải;

• ~s~ và ~t~ được gọi là ~k~-khớp ở vị trí ~i~ (~0 \le i < n~) nếu với mọi ~j~ (~0 \le j < k~) ta có ~s_{(i + j) \% n} = t_{(i + j) \% n}~ hoặc ~t_{(i + j) \% n} =~'*';

• Độ trùng khớp của tấm vé này với giải độc đắc sẽ là số lượng vị trí ~k~-khớp của ~s~ và ~t~.

Khi mua một tấm vé có mã số ~t~, bạn sẽ nhận được thông tin về độ trùng khớp của tấm vé này với giải độc đắc. Nếu độ trùng khớp bằng ~n~ và xâu ~t~ không chứa kí tự '*' nào thì bạn mới trúng giải độc đắc.

Yêu cầu: Bạn được phép mua vé nhiều lần, mỗi lần một vé, hãy sử dụng càng ít tiền càng tốt để mua và trúng được giải độc đắc.

Input

Thí sinh cần cài đặt hàm void run(int n, int k) đặt trong file lotte.cpp. Trong file lotte.cpp thí sinh cần phải khai báo thư viện bằng dòng lệnh #include "lottelib.h" (xem thêm các file mẫu trong mục đính kèm trên hệ thống để hiểu hơn về cách tương tác với hệ thống, các file này chỉ để thí sinh hiểu cách thức tương tác, không phải dùng để chấm bài).

Trong hàm run, mỗi lần mua vé bạn cần gọi hàm int buy(string t) với ~t~ là một xâu độ dài ~n~ chỉ chứa các kí tự '0', '1', '*' là mã của tấm vé bạn muốn mua (hàm này được cung cấp trong thư viện lotte.h. Hàm sẽ trả về độ trùng khớp của tấm vé này với giải độc đắc.

Chương trình sẽ tự động kết thúc nếu như một trong các tình huống sau xảy ra:

• Bạn mua được tấm vé trúng giải độc đắc;

• Tham số ~t~ truyền vào hàm buy là không hợp lệ;

• Chương trình của bạn sinh lỗi hoặc chạy quá thời gian quy định.

Output

Scoring

Có tất cả ~3~ subtask. Với mỗi test trong một subtask, cách tính ~\%~ điểm như sau:

• Nếu bạn trúng giải độc đắc, gọi ~T~ là tổng số tiền đã sử dụng, điểm của test đó là:

  • ~100\%~ số điểm nếu ~T < 0.75n^2~;

  • ~100\% \times \dfrac{1.1n^2 - T}{0.35n^2}~ số điểm nếu ~0.75n^2 \le T \le 1.1n^2~;

  • ~0\%~ số điểm nếu ~1.1n^2 < T~.

• Ngược lại, bạn được ~0~ điểm cho test đó.

Với mỗi subtask, gọi ~e~ là ~\%~ điểm nhỏ nhất mà thí sinh đạt được trong các test, ~score~ là điểm của subtask, khi đó điểm cho subtask được tính bằng ~e \times score~.

Notes

Với ~s =~"10111", ~n = 5~, ~k = 2~, hàm run sẽ được gọi với giá trị các tham số tương ứng là run(5,2), dưới đây là một ví dụ cách gọi lần lượt các hàm buy cho phép bạn trúng giải độc đắc: