Nhà khoa học máy tính người Hà Lan Edsger Dijkstra có nhiều đóng góp quan trọng, trong đó có thuật toán tìm đường đi ngắn mang tên ông. Bài này không nói về thuật toán đó.

Bạn bị trừ một điểm trong bài thi thuật toán vì viết sai “Dijkstra”: giữa D và stra, bạn viết một số ký tự, mỗi ký tự là i, j hoặc k. Bạn định tranh luận để lấy lại điểm bằng quaternion, một hệ số có thật (mở rộng từ số phức) với cấu trúc phép nhân sau:

Muốn nhân hai quaternion, tra hàng của số thứ nhất và cột của số thứ hai. Ví dụ \(i\times j=k\), còn \(j\times i=-k\).

Như các ví dụ cho thấy, phép nhân quaternion không giao hoán: tồn tại \(a,b\) sao cho \(a\times b\ne b\times a\). Tuy nhiên nó có tính kết hợp: với mọi \(a,b,c\), \(a\times(b\times c)=(a\times b)\times c\).

Dấu âm tuân theo quy tắc thông thường: \((-a)\times(-b)=a\times b\) và \((-a)\times b=a\times(-b)=-(a\times b)\).

Bạn muốn chứng minh phần viết sai tương đương với ijk bằng cách cắt chuỗi tại hai vị trí thành ba chuỗi con không rỗng, sao cho chuỗi trái rút gọn bằng phép nhân quaternion thành \(i\), chuỗi giữa thành \(j\), chuỗi phải thành \(k\). Ví dụ, jij được hiểu là \(j\times i\times j\); \(j\times i=-k\) và \((-k)\times j=i\), nên jij rút gọn thành \(i\). Nếu làm được, bạn sẽ lấy lại điểm. Hãy xác định có thể cắt như vậy hay không.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\).

Mỗi test gồm một dòng chứa hai số nguyên \(L,X\), rồi một dòng chứa \(L\) ký tự, tất cả đều là i, j hoặc k. Chuỗi không chứa dấu âm, 1 hay ký tự nào khác. Chuỗi cần xét là chuỗi \(L\) ký tự đã cho lặp lại \(X\) lần. Chẳng hạn, với \(L=4\), \(X=3\) và chuỗi kiij, chuỗi đầy đủ là kiijkiijkiij.

Dữ liệu ra

Với mỗi test, in Case #x: y, trong đó \(x\) bắt đầu từ 1 và \(y\) là YES hoặc NO tùy chuỗi có thể chia thành ba phần cho tích lần lượt \(i,j,k\) hay không.

Ràng buộc

• \(1\le T\le100\).
• \(1\le L\le10000\).

Phân nhóm

• Nhỏ: \(1\le X\le10000\), \(1\le L X\le10000\).
• Lớn: \(1\le X\le10^{12}\), \(1\le L X\le10^{16}\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

5
2 1
ik
3 1
ijk
3 1
kji
2 6
ji
1 10000
i

Case #1: NO
Case #2: YES
Case #3: NO
Case #4: YES
Case #5: NO

Nguồn

Google Code Jam 2015, Vòng loại, bài Dijkstra.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.