Cidoai的猫猫
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Cidoai 喜欢猫猫。
它有一个长度 n 的仅由小写字符构成的字符串 s，每个字符代表一只猫猫的品种。它想要合并一些长为 k 的子串，从而得到一个新的字符串 t。
我们记 t_{[i,j]} 表示由字符串 t 中第 i 位到第 j 位的字符构成的子串。
字符串 s 一共有 n-k+1 个长为 k 的子串，按照左端点从左往右的顺序分别记为 p_1,p_2,\cdots,p_{n-k+1}。使得存在一个非负整数序列 a 同时满足如下三个条件：
  • a_1=0。
  • \forall i \in [1,n-k],0 \le a_{i+1}-a_i \le 1；
  • \forall i \in [1,n-k+1],p_{i}=t_{[i-a_i,i+k-1-a_i]}；
设对于 k 生成的 t 的最短长度为 l_k。
举例而言：对于字符串 s=\text{aabbbaaa} 以及 k=2 的情况。p_1=\text{aa},p_2=\text{ab},p_3=\text{bb},p_4=\text{bb},p_5=\text{ba},p_6=\text{aa},p_7=\text{aa}。
最短的满足条件的字符串 t 为 \text{aabbaa}，对应的 a=\{0,0,0,1,1,1,2\}。
由于 Cidoai 想要尝试不同的可能性，它想让你求出对于 k=1,2,\cdots,n 的 l_k。为了避免输出量过大，它只需要你输出 (1 \times l_1)\oplus(2 \times l_2) \oplus \cdots \oplus (n \times l_n)。

输入描述:

第一行一个正整数 n 表示字符串长度。

第二行一个字符串 s。

1 \le n \le 5 \times 10^6。保证字符串仅由小写字母构成。

输出描述:

一行一个整数表示答案。
示例1

输入

复制 
4
baac

输出

复制 
23

说明

对于 k=1，令 t=\text{bac}，则 a=\{0,0,1,1\} 满足条件，l_1=3。对于 k=2,3,4，只有 t=\text{baac},a=\{0,0,0,0\} 满足条件，l_2=l_3=l_4=4。

因此 (1 \times 3) \oplus (2\times 4) \oplus (3 \times 4) \oplus (4 \times 4)=23。
示例2

输入

复制 
5
ababc

输出

复制 
13

说明

对于 k=1,2,3,4,5，只有 t=\text{ababc} 满足 l_k=5 最小。
示例3

输入

复制 
15
ababbbabaccaabb

输出

复制 
247
示例4

输入

复制 
20
ababcabbbbabaccaaabb

输出

复制 
134

备注: