Ông già Noel và các phụ tá thường trao đổi thông điệp bí mật bằng ngôn ngữ 25. Bảng chữ cái của ngôn ngữ này gồm 25 chữ cái Latin in hoa từ A đến Y, theo thứ tự thông thường; không có chữ Z.

Mỗi từ chứa đúng 25 chữ cái khác nhau. Viết từ vào bảng \(5\times5\) theo từng hàng, từ trái sang phải và từ trên xuống dưới. Một từ hợp lệ phải có các chữ cái tăng dần trên mỗi hàng và mỗi cột.

Ví dụ, từ ADJPTBEKQUCGLRVFINSWHMOXY cho bảng:

A D J P T
B E K Q U
C G L R V
F I N S W
H M O X Y

Đây là một từ hợp lệ. Ngược lại, ADJPTBEGQUCKLRVFINSWHMOXY không hợp lệ vì thứ tự tăng dần bị vi phạm ở cột thứ hai và cột thứ ba.

Ông già Noel có một từ điển gồm tất cả các từ hợp lệ, sắp xếp theo thứ tự từ điển và đánh số từ \(1\). Chẳng hạn, từ số 1 là ABCDEFGHIJKLMNOPQRSTUVWXY; từ số 2 là ABCDEFGHIJKLMNOPQRSUTVWXY, trong đó T và U đổi chỗ so với từ đầu tiên. Từ điển có không quá \(2^{31}\) từ.

Hãy xác định số thứ tự của một từ hợp lệ cho trước, hoặc tìm từ ứng với một số thứ tự cho trước.

Dữ liệu vào

Đọc từ đầu vào chuẩn hai dòng:

• Dòng đầu chứa một ký tự W hoặc N.
• Nếu ký tự đó là W, dòng thứ hai chứa một từ hợp lệ gồm 25 chữ cái.
• Nếu ký tự đó là N, dòng thứ hai chứa số thứ tự của một từ có trong từ điển.

Dữ liệu ra

In một dòng ra đầu ra chuẩn: số thứ tự của từ nếu chế độ là W, hoặc từ tương ứng nếu chế độ là N.

Chấm điểm

Có 20 bộ kiểm tra, mỗi bộ tương ứng 5 điểm trong thang điểm gốc 100. Kết quả đúng và trong giới hạn thời gian nhận toàn bộ điểm của bộ kiểm tra; ngược lại nhận 0 điểm.

Ví dụ

W
ABCDEFGHIJKLMNOPQRSUTVWXY

2

N
2

ABCDEFGHIJKLMNOPQRSUTVWXY

Nguồn

Đề gốc IOI 2001. Bảng tổng quan ngày 1.