You are given a list of n labels. Define the prefix score of a label w as follows: for each non-empty prefix p of w, count how many labels in the whole list (including w itself, and counting duplicates) have p as a prefix, and add up those counts over all prefixes of w.
Output the prefix score of each label, in the input order. All labels consist of lowercase English letters only.
Input format
Line 1: an integer n.
Line 2: n space-separated labels.
Output format
A single line with n space-separated integers: the prefix score of each label, in input order.
Constraints
- 1 <= n <= 100000
- Each label has length 1..30, lowercase letters.