{"raw_statement":[{"iden":"problem statement","content":"Let the **similarity** $f(X,Y)$ between two strings $X$ and $Y$ be the length of their longest common prefix.  \nFor example, the similarity between `abc` and `axbc` is $1$, and the similarity between `aaa` and `aaaa` is $3$.\nYou are given a string $S$ of length $N$. Let $S_i$ be the suffix of $S$ beginning with the $i$\\-th character of $S$. For each $k=1,\\ldots,N$, find $f(S_k,S_1)+f(S_k,S_2)+\\ldots+f(S_k,S_N)$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 10^6$\n*   $S$ is a string of length $N$ consisting of lowercase English letters."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$S$"},{"iden":"sample input 1","content":"3\nabb"},{"iden":"sample output 1","content":"3\n3\n2\n\n$S_1$ is `abb`, $S_2$ is `bb`, and $S_3$ is `b`.\n\n*   For $k=1$: $f(S_1,S_1)+f(S_1,S_2)+f(S_1,S_3)=3+0+0=3$.\n*   For $k=2$: $f(S_2,S_1)+f(S_2,S_2)+f(S_2,S_3)=0+2+1=3$.\n*   For $k=3$: $f(S_3,S_1)+f(S_3,S_2)+f(S_3,S_3)=0+1+1=2$."},{"iden":"sample input 2","content":"11\nmississippi"},{"iden":"sample output 2","content":"11\n16\n14\n12\n13\n11\n9\n7\n4\n3\n4"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}