题目描述

给出 $n$ 个字符串，第 $i$ 个字符串为 $s_i$。

定义函数 $f(i,j)$ 的计算方式如下：

• 只考虑前 $i$ 个给出的字符串。

• 将字符串划分出若干组，每组有恰好 $j$ 个字符串。

• 一组的值为这组所有字符串的最长公共前缀 (lcp) 的长度，一个划分方案的值为所有组的值的和。

• $f(i,j)$ 为最大的划分方案的值。

对于 $1\leq i\leq n$，求出 $\bigoplus_{j=1}^{i}(f(i,j)\times j)$，$\bigoplus$ 表示整数二进制异或运算。

本题采用子任务捆绑测试。

输入格式

第一行一个整数 $taskid$ ，表示子任务编号。 $taskid=0$ 表示样例。

接下来一行一个整数 $n$，表示字符串的数量。

接下来 $n$ 行，每行一个字符串，表示 $s_i$。

输出格式

输出 $n$ 行，每行一个整数，第 $i$ 行输出的整数表示 $\bigoplus_{j=1}^{i}(f(i,j)\times j)$。

样例

样例输入 1

0
5
aa
ab
ab
ac
d

样例输出 1

2
6
1
9
8

其余样例见下发文件。

• ex_journey2 与子任务 $1$ 的限制一致，

• ex_journey3 与子任务 $4$ 的限制一致，

• ex_journey4 与子任务 $5$ 的限制一致，

时空限制与数据范围

2s, 1024MB

记 $S=\sum_{i=1}^{n}|s_i|$

对于所有的数据：

• $n\leq 5\times 10^{5}, S\leq 10^{6}$

特殊性质 A: $s_i=$ a，

特殊性质 B: $|s_i|\leq 5$。