Mehmet là người yêu thích trò chơi máy tính và đã chơi Immortal Grasshopper suốt 10 giờ qua. Immortal Grasshopper là trò chơi máy tính trong đó bạn dùng các nút để điều khiển nhân vật của mình, một con châu chấu bậc thầy karate. Đối thủ của bạn là một con kiến do máy tính điều khiển.

Châu chấu có thể thực hiện tổng cộng $S$ ($1 \le S \le 4$) kiểu tấn công khác nhau. Các kiểu tấn công này được đặt tên bằng $S$ chữ cái đầu tiên của bảng chữ cái. Ví dụ:

• $S = 2$: các kiểu tấn công có tên $A$, $B$.
• $S = 4$: các kiểu tấn công có tên $A$, $B$, $C$, $D$.

Mỗi đòn tấn công trúng đối thủ gây 1 điểm sát thương.

Tuy biết luật chơi, nhưng vì Mehmet đã ngủ thiếp đi sau 10 giờ chơi nên không có ai chỉ bạn cách điều khiển. Bạn tìm thấy trên bàn một bộ điều khiển có $N$ nút (các nút được đánh số từ $0$ đến $N - 1$). Sau khi chơi một lúc, bạn nhận ra mỗi nút có thể thực hiện một trong $S$ kiểu tấn công, nhưng không biết nút nào thực hiện kiểu nào. May mắn là nhờ nhãn dán trên nút đầu tiên, bạn biết nó thực hiện tấn công kiểu $A$. Hơn nữa, bạn biết rằng mỗi kiểu tấn công khác nhau được gán cho ít nhất một nút.

Nhiệm vụ của bạn là xác định kiểu tấn công của tất cả các nút trên bộ điều khiển bằng cách chơi trò chơi này.

Bạn chơi theo mô tả dưới đây. Để tấn công đối thủ kiến, bạn dùng các tổ hợp nút liên tiếp, gọi là combo. Một combo hoạt động như sau:

• Bạn tạo combo bằng cách nhấn liên tiếp một số lượng nút tùy ý.
• Bạn có thể nhấn các nút theo bất kỳ thứ tự nào trong một combo.
• Cùng một nút có thể được nhấn nhiều lần trong một combo.
• Một combo có độ dài tối đa $400$.

Trò chơi tiếp nhận các thao tác của bạn và cuối cùng cho biết tổng sát thương bạn đã gây ra.

Sát thương một combo gây cho kiến được tính như sau. Gọi $t(X)$ là kiểu tấn công đứng ngay sau kiểu $X$ theo thứ tự chữ cái. Với kiểu tấn công biểu diễn bởi chữ cái cuối cùng, $t(X)$ được định nghĩa là kiểu $A$. Ví dụ:

• Với $S = 4$: $t(A) = B$, $t(B) = C$, $t(C) = D$, $t(D) = A$.
• Với $S = 2$: $t(A) = B$, $t(B) = A$.

Đối thủ kiến có thể chống lại một số đòn tấn công của bạn bằng những chiến thuật tinh ranh. Cụ thể, nếu đòn tấn công thành công (không bị chặn) gần nhất gây sát thương là kiểu $X$, và bạn dùng kiểu $t(X)$ cho đòn tiếp theo, kiến sẽ chặn đòn $t(X)$ và bạn không gây sát thương. Nếu không thể chặn, bạn gây 1 điểm sát thương cho kiến (đòn đầu tiên luôn gây sát thương).

Mục tiêu của bạn là tìm và báo kiểu tấn công của tất cả các nút bằng tổng số combo ít nhất.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau:

std::string olumsuz_cekirge(int N, int S)

• Giá trị $N$ biểu diễn số nút trên bộ điều khiển.
• Giá trị $S$ biểu diễn số kiểu tấn công khác nhau trong trò chơi.
• Hàm này phải trả về một string độ dài $N$, biểu diễn các kiểu tấn công được gán cho các nút.

Trong quá trình thực hiện, bạn có thể dùng hàm kombo dưới đây:

int kombo(std::vector<int> buton)

• Bạn có thể gọi hàm kombo nhiều nhất $400$ lần trong mỗi lời gọi olumsuz_cekirge.
• Mảng buton chỉ định chỉ số các nút bạn muốn dùng trong combo.
• Các giá trị trong mảng buton phải là số nguyên từ $0$ đến $N - 1$.
• Độ dài mảng buton không được vượt quá $400$.

Bạn cần giải $T$ kịch bản độc lập trong mỗi lần kiểm thử với cùng các giá trị $N$ và $S$. Với mỗi kịch bản độc lập, hàm olumsuz_cekirge được gọi một lần.

Giới hạn

• $1 \le T \le 100$
• $4 \le N \le 400$
• $1 \le S \le 4$
• Trình chấm không thích nghi. Cụ thể, dữ liệu vào được cố định trước khi gọi hàm olumsuz_cekirge và không thay đổi trong quá trình thao tác.

Nhiệm vụ con

Điểm nhận được ở nhiệm vụ con thứ $i$ sẽ là $0$ nếu trong bất kỳ kịch bản nào hàm kombo được gọi với tham số không đáp ứng các tiêu chí trên, hoặc hàm olumsuz_cekirge trả về kết quả sai. Nếu không, điểm bằng công thức sau:

$$P_i \times \min\left(1,\left(\frac{400-q}{400-Q_i}\right)^3\right)$$

• Giá trị $P_i$ biểu diễn tổng điểm có thể nhận được ở nhiệm vụ con thứ $i$.
• Giá trị $q$ biểu diễn số lần gọi hàm kombo lớn nhất trong các kịch bản của tất cả các lần kiểm thử thuộc nhiệm vụ con thứ $i$.
• Các giá trị $Q_i$ được cho trong mô tả các nhiệm vụ con.

Ví dụ

olumsuz_cekirge(6, 3)

Trong các ví dụ, kiểu tấn công tương ứng với từng nút lần lượt là ABCBBA, nên hàm này phải trả về chuỗi đó.

kombo([0, 1, 2])

Lời gọi trên trả về $2$. Các đòn trong combo này là $ABC$. Đòn $A$ đầu tiên đánh trúng. Đòn $B$ bị chặn. Vì đòn gây sát thương gần nhất là $A$, kiến không thể chặn đòn $C$ và nhận sát thương.

kombo([0, 0, 0])

Lời gọi trên trả về $3$. Các đòn trong combo này là $AAA$. Tất cả các đòn $A$ đều gây sát thương.

kombo([5, 1, 3, 2, 2, 0])

Lời gọi trên trả về $3$. Các đòn trong combo này là $ABBCCA$. Đòn $A$ đầu tiên đánh trúng. Đòn $B$ bị chặn. Vì đòn đánh trúng gần nhất vẫn là $A$, đòn $B$ thứ hai cũng bị chặn. Đòn $C$ thứ nhất và thứ hai đều gây sát thương. Vì đòn đánh trúng gần nhất là $C$, đối thủ kiến chờ đòn $A$, nên đòn $A$ cuối cùng bị chặn.

kombo([2, 2, 1])

Lời gọi trên trả về $3$. Các đòn trong combo này là $CCB$. Tất cả các đòn đều gây sát thương.

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu vào theo định dạng sau, trong đó $C_i$ là chuỗi độ dài $N$ biểu diễn các kiểu tấn công bí mật của các nút trong kịch bản thứ $i$:

$$\begin{gathered}T\ N\ S\\C_1\\C_2\\\ldots\\C_T\end{gathered}$$

Với mỗi kịch bản, trình chấm in như sau: Nếu giải đúng kịch bản, tổng số thao tác đã dùng được in ra. Nếu có lỗi, một trong các thông báo lỗi sau được in ra:

Yanlis cevap (Wrong answer)
Buton asildi (Button limit exceeded)
Yanlis buton (Invalid button)
Kombo asildi (Combo limit exceeded)

• Yanlis cevap (Wrong answer): Được in nếu đáp án của bất kỳ nút nào có sai sót.
• Buton asildi (Button limit exceeded): Được trả về nếu dùng hơn $400$ nút trong một lời gọi hàm kombo.
• Yanlis buton (Invalid button): Được trả về nếu một chỉ số nút không phải số từ $0$ đến $N - 1$ trong một lời gọi hàm kombo.
• Kombo asildi (Combo limit exceeded): Được trả về nếu hàm kombo được gọi hơn $400$ lần trong một lời gọi hàm olumsuz_cekirge.