EIU Programming Practices and Exams

Cho thư mục gốc, và dữ liệu mô tả cây thư mục (Folder Tree), gồm có thư mục (Folder) và tập tin (File). Ta biết rằng tên File và Folder là duy nhất, và không có thư mục nào trống. Hãy viết chương trình tìm tất cả thư mục có chứa File mà tên của File chứa chuỗi cho trước, việc tìm kiếm không phân biệt chữ hoa chữ thường.

Input

Dòng đầu tiên chứa số nguyên n, là số tập tin và thư mục (kể cả thư mục gốc) (n ≤ 10⁵)

n -1 dòng tiếp theo gồm 2 từ a­_i , b_i, thể hiện thư mục a­_i chứa b_i hoặc thư mục b_i chứa a­_i. a­_i , b_i chỉ bao gồm ký tự và chữ số trong tập [a-zA-Z0-9] (|a_i|, |b_i| ≤ 50).

Dòng tiếp theo là tên thư mục gốc.

Dòng tiếp theo chứa từ s, là từ khóa cần tìm trong tên các tập tin (|s| ≤ 10).

Output

Xuất ra tên của thư mục chứa ít nhất một file cần tìm, và tổng số file thư mục đó chứa (tìm kiếm đệ quy vào các thư mục bên trong). Tên thư mục cha luôn được in ra (nếu có chứa file thỏa yêu cầu) sau khi đã in tên các thư mục con.

Mỗi kết quả xuất ra trên một dòng. Tại mỗi thư mục, tìm kiếm theo thứ tự alphabet của các thư mục con.

Example

Input:
7
documents DataMining
Report DataMining
Web documents
Web Source
Source Libary
Web Angular
documents
ar

Output:
Source 1
Web 2
documents 2