문제
사람과 비슷하게, 소들은 가끔 그들이 어떤 방식으로든 특별하기를 원한다. 때문에 농부 존의 소들은 모두 같은 품종이고 비슷하게 생겼지만, 그들은 이름에서 독창성을 가지기를 원한다.
모든 소들의 이름은 몇몇의 substring을 가지고 있다. 예를 들어, “amy”는 substring으로 {a, m, y, am, my, amy}를 가지고 있으며, “tommy”는 substring으로 {t, o, m, y, to, om, mm, my, tom, omm, mmy, tomm, ommy, tommy}를 가진다.
소의 이름에는 “uniqueness factor”가 있으며, 이 값은 다른 소의 substring과 공유하지 않는 substring를 의미한다. 예를 들어, 만약 amy가 혼자 무리에 있다면, 그녀의 uniqueness는 6이다. tommy가 혼자 무리에 있다면 uniqueness는 14이며, 둘이 같이 있다면 amy의 uniqueness는 3, tommy의 uniqueness는 11이다.
무리에 속한 소들의 이름이 주어졌을 때, 각 소들에 대한 uniqueness factor를 구하여라.
입력
첫 번째 줄에는 소의 마리수를 의미하는 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)
다음 N개의 줄에는 각 소의 이름이 알파벳 소문자로 이루어진 문자열로 주어진다. 모든 이름의 길이 합은 105를 넘지 않는다.
출력
N개의 줄에, 각 소에 대한 uniqueness factor를 한 줄에 하나씩 출력한다.
예제
3
amy
tommy
bessie
3
11
19
로그인해야 코드를 작성할 수 있어요.