Farmer John thích sưu tầm càng nhiều giống bò khác nhau càng tốt. Trên thực tế, ông đã sưu tầm gần như mọi giống bò có thể hình dung được, chỉ trừ một vài giống được ghi trong một danh sách ngắn gồm \(N\) dòng (\(1 \le N \le 100\)). Danh sách trông như sau:

Farmer John has no large brown noisy cow.
Farmer John has no small white silent cow.
Farmer John has no large spotted noisy cow.

Mỗi mục trong danh sách mô tả một con bò còn thiếu bằng một danh sách ngắn các tính từ, và mọi mục đều có cùng số lượng tính từ (trong ví dụ này là 3). Số tính từ trên mỗi dòng nằm trong khoảng \(2..30\).

Farmer John có một con bò ứng với mọi tổ hợp tính từ khả dĩ khác không xuất hiện trong danh sách. Trong ví dụ này, tính từ thứ nhất có thể là large hoặc small, tính từ thứ hai có thể là brown, white hoặc spotted, và tính từ thứ ba có thể là noisy hoặc silent. Như vậy có \(2 \times 3 \times 2 = 12\) tổ hợp khác nhau, và Farmer John có một con bò ứng với mỗi tổ hợp, ngoại trừ những tổ hợp được nêu cụ thể trong danh sách. Trong ví dụ này, một con bò large white noisy là một trong 9 con bò của ông. Farmer John chắc chắn rằng mình có nhiều nhất \(1\,000\,000\,000\) con bò.

Nếu Farmer John liệt kê những con bò của mình theo thứ tự từ điển, con bò thứ \(K\) trong danh sách này là con nào?

Dữ liệu vào

• Dòng 1 chứa hai số nguyên \(N\) và \(K\).
• Các dòng \(2..1+N\): mỗi dòng là một câu có dạng Farmer John has no large spotted noisy cow.. Mỗi tính từ trong câu là một xâu gồm nhiều nhất 10 chữ cái thường. Bạn biết câu đã kết thúc khi gặp xâu cow. có dấu chấm ở cuối.

Dữ liệu ra

• Dòng 1 chứa mô tả của con bò thứ \(K\) trong trang trại.

Phân nhóm

Trong 10 test của bài toán này:

• Các test \(2..4\) có nhiều nhất hai tính từ trên mỗi dòng trong danh sách của Farmer John.
• Các test \(2..6\) có đúng hai giá trị khả dĩ cho mỗi tính từ. Trong tất cả các test còn lại, mỗi tính từ có từ 1 đến \(N\) giá trị khả dĩ.

Ví dụ

3 7
Farmer John has no large brown noisy cow.
Farmer John has no small white silent cow.
Farmer John has no large spotted noisy cow.

small spotted noisy

large brown silent
large spotted silent
large white noisy
large white silent
small brown noisy
small brown silent
small spotted noisy
small spotted silent
small white noisy

Nguồn

USACO 2013 November Contest, Silver — Problem 1: Farmer John has no Large Brown Cow

Tác giả đề: Brian Dean, 2013.