Có ba cọc \(A, B, C\) và có \(N\) chiếc đĩa đánh số từ \(1\) đến \(N\) có kích thước tương ứng là \(1, 2, \dots, N\). Trạng thái ban đầu cả \(N\) chiếc đĩa đều ở cọc \(A\), và đĩa to luôn ở dưới đĩa nhỏ. Xét phương pháp chuyển đĩa sau để chuyển đĩa từ cọc \(A\) sang cọc \(C\) sao cho các đĩa to luôn luôn ở dưới các đĩa nhỏ:

Gọi thủ tục Chuyen(N, A, B, C). Trong đó:

void Move(int n, int c1, int c3) {
    if (n == 1) {
        // chuyển đĩa nằm trên cùng c1 sang c3;
    } else {
        int c2 = 6 - c1 - c3;
        Move(n - 1, c1, c2);
        Move(1, c1, c3);
        Move(n - 1, c2, c3);
    }
}

Thủ tục Move(n, c1, c3) có nghĩa là ta chuyển \(n\) đĩa trên cùng của cọc \(c1\) sang cọc \(c3\).

Xét hai bài toán sau để giải quyết:

1. Cho số \(P\) (\(P < 2^N\)), hỏi sau lần gọi hàm Move(1, ...) thứ \(P\) thì trạng thái của \(N\) đĩa như thế nào?
2. Cho trước một trạng thái của \(N\) đĩa, bạn hãy xét xem trạng thái đó có xuất hiện trong quá trình chuyển đĩa từ \(A\) sang \(C\) theo phương pháp trên hay không? Nếu có xuất hiện thì đó là sau lần gọi hàm Move(1, ...) thứ bao nhiêu? (Giả sử là số \(Q\)).

Input

• Dòng 1: Ghi số \(N\) (\(N \le 100\)).
• Dòng 2: Ghi số \(P\).
• Dòng 3: Ghi một xâu gồm \(N\) ký tự chỉ gồm A, B, C là trạng thái của các đĩa (ký tự thứ \(i\) là vị trí của đĩa kích thước \(i\)). Dữ liệu đảm bảo các đĩa to luôn luôn ở dưới các đĩa nhỏ tại mỗi cọc.

Output

• Dòng 1: Ghi một xâu gồm \(N\) ký tự là trạng thái đĩa sau lần gọi thứ \(P\).
• Dòng 2: Ghi số \(Q\) (\(Q = -1\) nếu trạng thái đó không tồn tại).

Example

3
2
CCC

CBA
7

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(N \le 20\).
• Subtask \(2\) (\(40\%\) số điểm): \(N \le 63\).
• Subtask \(3\) (\(40\%\) số điểm): \(N \le 100\).