Nổi Bật Trong Đàn

Farmer John muốn biết điều gì khiến mỗi con bò trong đàn của ông trở nên đặc biệt. Ông đặt cho con bò thứ $i$ một cái tên là chuỗi $s_i$.

Một xâu con của $s_i$ là một đoạn ký tự liên tiếp trong $s_i$ (không phải dãy con rời rạc). Hai xâu con giống hệt nhau, dù nằm ở những vị trí khác nhau trong cùng một chuỗi, vẫn chỉ được tính là một.

Với mỗi con bò $i$, hãy đếm số lượng xâu con phân biệt của $s_i$ mà không xuất hiện như một xâu con của bất kỳ chuỗi $s_j$ nào khác ($j\ne i$).

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $N$ ($1\le N\le {10}^5$).
• $N$ dòng tiếp theo, dòng thứ $i$ chứa chuỗi $s_i$, tên của con bò thứ $i$, chỉ gồm các chữ cái thường.
• Tổng độ dài của tất cả $N$ chuỗi không vượt quá ${10}^5$.

Dữ liệu ra

In ra $N$ dòng, dòng thứ $i$ chứa một số nguyên: số lượng xâu con phân biệt của $s_i$ không xuất hiện trong bất kỳ chuỗi nào khác.

Kết quả có thể lên tới khoảng $5\times {10}^9$ nên cần dùng kiểu số nguyên 64 bit.

Ràng buộc

• $1\le N\le {10}^5$
• Tổng độ dài tất cả chuỗi $\le {10}^5$
• Mỗi $s_i$ chỉ gồm chữ cái thường (a-z)

Ví dụ